diff options
Diffstat (limited to 'meowpp/dsa/SegmentTree.h')
| -rw-r--r-- | meowpp/dsa/SegmentTree.h | 100 |
1 files changed, 54 insertions, 46 deletions
diff --git a/meowpp/dsa/SegmentTree.h b/meowpp/dsa/SegmentTree.h index 585ea5d..89fd5d9 100644 --- a/meowpp/dsa/SegmentTree.h +++ b/meowpp/dsa/SegmentTree.h @@ -2,6 +2,30 @@ #define SegmentTree_H__ namespace meow{ + //# + //#=== meow:: *SegmentTree<Value>* (C++ class) + //#==== Description + //# 維護一個陣列, 並且讓user可以有區間查詢, 區間修改的小東東 + //# + //#==== Template Class Operators Request + //#[options="header",width="70%",cols="1>m,1<,3<s,5<,3<,15<",grid="rows"] + //#|===================================================================== + //#|Const?|Typename| Operator | Parameters |Return_Type| Description + //#|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|` 為 '回傳相加值' + //# template<class Value> class SegmentTree{ private: @@ -28,11 +52,38 @@ namespace meow{ SegmentTree(size_t __size); SegmentTree(SegmentTree const& __tree2); // + //#==== Support Methods + //# + //# * N <- `this` 所維護的陣列長度 + //# + //#[options="header",width="100%",cols="1>m,2>s,7<,3<,3^,20<",grid="rows"] + //#|===================================================================== + //#|Const?|Name | Parameters | Return_Type| Time_Complexity| Description + + + //#||reset|(size_t `size`)|void|O(1) + //#|將資料清空且設定維護範圍是 `0~size - 1` 其中時間複雜度確切多少未知 + //# 要看 `std::vector::resize()` 的效率 void reset(size_t __size); - // + + + //#|const|query|(ssize_t `first`,\ssize_t `last`)|Value|O(logN) + //#|回傳區間 `[first,last]` (邊界都含) 的區間值 Value query (ssize_t __first, ssize_t __last) const; + + + //#||override|(ssize_t `first`,\ssize_t `last`,\Value const& `value`) + //#|void|O(logN) + //#|將區間 `[first,last]` 全部都設定成 `value` void override(ssize_t __first, ssize_t __last, Value const& __value); + + + //#||offset|(ssize_t `first`,\ssize_t `last`,\Value const& `delta`) + //#|void|O(logN) + //#|將區間 `[first,last]` 全部都加上 `delta` void offset (ssize_t __first, ssize_t __last, Value const& __delta); + + // void print(){ for(int i = 0; i < _size; i++){ query(i, i); @@ -52,52 +103,9 @@ namespace meow{ printf("\n"); } } + + //#|============================================== }; - /********************************************************* - @asciidoc - === meow:: *SegmentTree<Value>* (C++ class) - .Description - `SegmentTree` is a data structure that can maintain an array, and - support *range update* , *range query* - - .Template Request - * `Value` should has - ** `operator+(Value)` offset - ** `operator|(Value)` merge two nodes - ** `operator*(size_t)` ?? - - For example, if you want to maintain *range minimum* - - * `Value::operator+(Value v2)` will be `this->realValue + v2.realValue` - * `Value::operator|(Value v2)` will be `std::min(this->realValue, v2.realValue)` - * `Value::operator*(size_t n)` will be `this->realValue` - - If you want to maintain *range sum* - - * `Value::operator+(Value v2)` will be `this->realValue + v2.realValue` - * `Value::operator|(Value v2)` will be `this->realValue + v2.realValue)` - * `Value::operator*(size_t n)` will be `this->realValue * n` - - .Support methods - * N <- array size - [options="header",width="100%",cols="1>,1<s,3<,1<,1<,10<",grid="rows"] - |======================================================================= - |Const?|Name| Parameters| Return Type| Time Complexity| Description - ||reset|(size_t N)|void|O(1)| - Clear and reset the array size to N (from `0` to `N - 1`) - |const|query|(ssize_t __first, ssize_t __last)|Value|O(logN)| - Range query - ||override|(ssize_t __first, ssize_t __last, Value const& __value)|void| - O(logN)| Let the element in the array index from `__first` to `__last` - be `__value` - ||offset|(ssize_t __first, ssize_t __last, Value const& __value)|void| - O(logN)| Let the element in the array index from `__first` to `__last` - plus `__value` - |======================================================================= - -''' -@asciidoc- - *********************************************************/ } #include "SegmentTree.hpp" |