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
|
#ifndef SegmentTree_H__
#define SegmentTree_H__
namespace meow{
template<class Value>
class SegmentTree{
private:
struct Node{
Value _value;
Value _offset;
bool _sameFlag;
//
Node();
};
//
size_t _size;
std::vector<Node> _nodes;
size_t const _root;
//
size_t leftChild(size_t __parent) const;
size_t rightChild(size_t __parent) const;
//
void downUpdate(size_t __L, size_t __R, size_t __index);
void override(size_t __l, size_t __r,
size_t __L, size_t __R,
size_t __index, Value const& __value);
void offset(size_t __l, size_t __r,
size_t __L, size_t __R,
size_t __index, Value const& __delta);
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);
};
/*********************************************************
@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-
*********************************************************/
}
#endif
|
