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 24 while(N>>=1) {
25 25 tree.resize(tree.size()+1); tree.back().resize(N);
26 26 for(int i=0; i<N; ++i)
27 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 32 return QueryRec(s, e, tree.size()-1, 0, tree[0].size());
33 33 }
34 34
35 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 37 SetRec(s, e, Node::One(v), tree.size()-1, 0, tree[0].size());
38 38 }
39 39
40 40 private:
41 41 void CalcMidNode(int lv, int idx)
42 42 {
43 43 tree[lv][idx] = Node::Concat(tree[lv-1][idx*2], tree[lv-1][idx*2+1]);