Templates -- Meow  1.2.9
A C++ template contains kinds of interesting classes and functions
Classes | Public Member Functions | List of all members
meow::SegmentTree< Value > Class Template Reference

中文名 線段樹 More...

#include "SegmentTree.h"

Public Member Functions

 SegmentTree ()
 constructor More...
 
 SegmentTree (size_t size)
 constructor, with size gived More...
 
 SegmentTree (SegmentTree const &tree2)
 constructor, 並且複製資料 More...
 
SegmentTree copyFrom (SegmentTree const &b)
 複製 More...
 
size_t size () const
 回傳size More...
 
void reset (size_t size)
 將資料清空且設定維護範圍是 0~size-1 More...
 
Value query (ssize_t first, ssize_t last) const
 回傳區間 [first,last] (邊界都含) 的區間值 More...
 
void override (ssize_t first, ssize_t last, Value const &value)
 將區間 [first,last] 全部都設定成 value More...
 
void offset (ssize_t first, ssize_t last, Value const &delta)
 將區間 [first,last] 全部都加上 delta More...
 
SegmentTree & operator= (SegmentTree const &b)
 same as copyFrom(b) More...
 

Detailed Description

template<class Value>
class meow::SegmentTree< Value >

中文名 線段樹

維護一個陣列, 並且讓user可以有區間查詢, 區間修改的小東東

Template Class Operators Request

const?TypenameOperator Parameters Return Type Description
const Vector operator[] (size_t n) Scalar 取得第 n 維度量
const Vector operator< (Vector v) bool 權重比較
const Scalar operator* (Scalar s) Scalar 相乘
const Scalar operator+ (Scalar s) Scalar 相加
const Scalar operator- (Scalar s) Scalar 相差
const Scalar operator< (Scalar s) bool 大小比較
const Value operator+ (Value v) Value 相加(位移)
const Value operator* (size_t n) Value 每個Value都一樣,

長為 n 的區間的值| |const |Value |operator{b}|(Value v) |Value | 區間合併後的值 |

  • 若要維護區間最小值, 即每次都是詢問範圍 [a, b] 的最小值, 則可以定義
    • operator+ 為 '回傳相加值'
    • operator* 為 '回傳*this'
    • operator| 為 '回傳std::min(*this, v)'
  • 若要維護區間最總和, 即每次都是詢問範圍 [a, b] 的總和, 則可以定義
    • operator+ 為 '回傳相加值'
    • operator* 為 '回傳(*this) * n'
    • operator| 為 '回傳相加值'
Author
cat_leopard

Definition at line 45 of file SegmentTree.h.

Constructor & Destructor Documentation

template<class Value >
meow::SegmentTree< Value >::SegmentTree ( )
inline

constructor

Definition at line 121 of file SegmentTree.h.

template<class Value >
meow::SegmentTree< Value >::SegmentTree ( size_t  size)
inline

constructor, with size gived

Definition at line 126 of file SegmentTree.h.

template<class Value >
meow::SegmentTree< Value >::SegmentTree ( SegmentTree< Value > const &  tree2)
inline

constructor, 並且複製資料

Definition at line 131 of file SegmentTree.h.

Member Function Documentation

template<class Value >
SegmentTree meow::SegmentTree< Value >::copyFrom ( SegmentTree< Value > const &  b)
inline

複製

Definition at line 138 of file SegmentTree.h.

template<class Value >
void meow::SegmentTree< Value >::offset ( ssize_t  first,
ssize_t  last,
Value const &  delta 
)
inline

將區間 [first,last] 全部都加上 delta

Definition at line 181 of file SegmentTree.h.

template<class Value >
SegmentTree& meow::SegmentTree< Value >::operator= ( SegmentTree< Value > const &  b)
inline

same as copyFrom(b)

Definition at line 187 of file SegmentTree.h.

template<class Value >
void meow::SegmentTree< Value >::override ( ssize_t  first,
ssize_t  last,
Value const &  value 
)
inline

將區間 [first,last] 全部都設定成 value

Definition at line 173 of file SegmentTree.h.

template<class Value >
Value meow::SegmentTree< Value >::query ( ssize_t  first,
ssize_t  last 
) const
inline

回傳區間 [first,last] (邊界都含) 的區間值

Definition at line 165 of file SegmentTree.h.

template<class Value >
void meow::SegmentTree< Value >::reset ( size_t  size)
inline

將資料清空且設定維護範圍是 0~size-1

Definition at line 154 of file SegmentTree.h.

template<class Value >
size_t meow::SegmentTree< Value >::size ( ) const
inline

回傳size

Definition at line 147 of file SegmentTree.h.

The documentation for this class was generated from the following file: