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
|
#ifndef SegmentTree_H__
#define SegmentTree_H__
namespace meow{
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);
//
void reset(size_t __size);
//
Value query (ssize_t __first, ssize_t __last) const;
void override(ssize_t __first, ssize_t __last, Value const& __value);
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");
}
}
};
/*********************************************************
@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"
#endif
|
