1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
|
#ifndef SegmentTree_H__
#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:
struct Node{
Value _value;
Value _offset;
bool _sameFlag;
};
//
size_t _size;
std::vector<Node> _nodes;
//
void update(size_t __index, size_t __size, Value const& __value,
bool __override);
void update(size_t __l, size_t __r, size_t __L, size_t __R,
size_t __index, Value const& __value,
bool __override);
Value query(size_t __l, size_t __r, size_t __L, size_t __R,
size_t __index);
//
bool rangeCorrect(ssize_t* __first, ssize_t* __last) const;
public:
SegmentTree();
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);
}
printf("\n");
for(int depth = 0, count = 1, size = _size, id = 0;
size > 0;
depth++, count *= 2, size /= 2){
for(int j = 0; j < count; j++, id++){
printf("[%3d%c%3d%*s]",
_nodes[id]._value.value,
_nodes[id]._sameFlag ? 's' : ' ',
_nodes[id]._offset.value,
size * 9 - 9,
"");
}
printf("\n");
}
}
//#|==============================================
};
}
#include "SegmentTree.hpp"
#endif
|
