-
Notifications
You must be signed in to change notification settings - Fork 0
/
DisjointSparseTable.cpp
51 lines (45 loc) · 1.64 KB
/
DisjointSparseTable.cpp
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
/*
* @title DisjointSparseTable
* @docs md/static-range-query/DisjointSparseTable.md
*/
template<class Operator> class DisjointSparseTable{
public:
using TypeNode = typename Operator::TypeNode;
size_t depth;
size_t length;
vector<TypeNode> node;
vector<size_t> msb;
DisjointSparseTable(const vector<TypeNode>& vec) {
for(depth = 0;(1<<depth)<=vec.size();++depth);
length = (1<<depth);
//msb
msb.resize(length,0);
for(int i = 0; i < length; ++i) for(int j = 0; j < depth; ++j) if(i>>j) msb[i] = j;
//init value
node.resize(depth*length,Operator::unit_node);
for(int i = 0; i < vec.size(); ++i) node[i] = vec[i];
for(int i = 1; i < depth; ++i) {
for(int r = (1<<i),l = r-1; r < length; r += (2<<i),l = r-1){
//init accumulate
node[i*length+l] = node[l];
node[i*length+r] = node[r];
//accumulate
for(int k = 1; k < (1<<i); ++k) {
node[i*length+l-k] = Operator::func_fold(node[i*length+l-k+1],node[l-k]);
node[i*length+r+k] = Operator::func_fold(node[i*length+r+k-1],node[r+k]);
}
}
}
}
//[l,r)
TypeNode fold(int l,int r) {
r--;
return (l>r||l<0||length<=r) ? Operator::unit_node: (l==r ? node[l] : Operator::func_fold(node[msb[l^r]*length+l],node[msb[l^r]*length+r]));
}
};
//sum
template<class T> struct NodeSum {
using TypeNode = T;
inline static constexpr TypeNode unit_node = 0;
inline static constexpr TypeNode func_fold(TypeNode l,TypeNode r){return l+r;}
};