Differences From Artifact [0226be12935bcdf4]:
- File
lib/dataStructure/segmentTree.cpp
- 2012-02-18 03:50:50 - part of checkin [58f56e668e] on branch trunk - Cleaned up segment tree for non-rannge-update case. (user: kinaba) [annotate]
To Artifact [f9b609a5f0b95ebf]:
- File
lib/dataStructure/segmentTree.cpp
- 2012-06-07 14:24:24 - part of checkin [34dd53bac9] on branch trunk - TCO12-2C (user: kinaba) [annotate]
24 while(N>>=1) { 24 while(N>>=1) {
25 tree.resize(tree.size()+1); tree.back().resize(N); 25 tree.resize(tree.size()+1); tree.back().resize(N);
26 for(int i=0; i<N; ++i) 26 for(int i=0; i<N; ++i)
27 CalcMidNode(tree.size()-1, i); 27 CalcMidNode(tree.size()-1, i);
28 } 28 }
29 } 29 }
30 30
31 Node Query(int s, int e) { // compute h( seq[s,e) ) : O(log n) | 31 Node Query(int s, int e) { // compute h( seq[s,e) ) : O(log n)
32 return QueryRec(s, e, tree.size()-1, 0, tree[0].size()); 32 return QueryRec(s, e, tree.size()-1, 0, tree[0].size());
33 } 33 }
34 34
35 template<typename Value> 35 template<typename Value>
36 void Set(int s, int e, Value v) { // seq[s,e):=v : O(log nE|e-s|) | 36 void Set(int s, int e, Value v) { // seq[s,e):=v : O(log n |e-s|)
37 SetRec(s, e, Node::One(v), tree.size()-1, 0, tree[0].size()); 37 SetRec(s, e, Node::One(v), tree.size()-1, 0, tree[0].size());
38 } 38 }
39 39
40 private: 40 private:
41 void CalcMidNode(int lv, int idx) 41 void CalcMidNode(int lv, int idx)
42 { 42 {
43 tree[lv][idx] = Node::Concat(tree[lv-1][idx*2], tree[lv-1][idx*2 43 tree[lv][idx] = Node::Concat(tree[lv-1][idx*2], tree[lv-1][idx*2