Differences From Artifact [d90f43e790c04822]:
- File
lib/dataStructure/segmentTree.cpp
- 2012-01-22 17:50:12 - part of checkin [ba4dea3538] on branch trunk - segment tree. (user: kinaba) [annotate]
To 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]
1 //------------------------------------------------------------- 1 //-------------------------------------------------------------
2 // Segment tree 2 // Segment tree
3 // in some general form 3 // in some general form
4 // 4 //
5 // Verified by 5 // Verified by
> 6 // - Codeforces 107 C
6 // - Codeforces 104 E 7 // - Codeforces 104 E
7 //------------------------------------------------------------- 8 //-------------------------------------------------------------
8 9
> 10 template<typename Node>
> 11 class SegmentTree
> 12 {
> 13 public:
> 14 template<typename Seq>
> 15 SegmentTree(const Seq& s) {
> 16 int N = 1;
> 17 while( N < s.size() )
> 18 N <<= 1;
> 19
> 20 tree.resize(tree.size()+1); tree.back().resize(N);
> 21 for(int i=0; i<N; ++i)
> 22 tree.back()[i] = i<s.size() ? Node::One(s[i]) : Node::Ze
> 23
> 24 while(N>>=1) {
> 25 tree.resize(tree.size()+1); tree.back().resize(N);
> 26 for(int i=0; i<N; ++i)
> 27 CalcMidNode(tree.size()-1, i);
> 28 }
> 29 }
> 30
> 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());
> 33 }
> 34
> 35 template<typename Value>
> 36 void Set(int s, int e, Value v) { // seq[s,e):=v : O(log nE|e-s|)
> 37 SetRec(s, e, Node::One(v), tree.size()-1, 0, tree[0].size());
> 38 }
> 39
> 40 private:
> 41 void CalcMidNode(int lv, int idx)
> 42 {
> 43 tree[lv][idx] = Node::Concat(tree[lv-1][idx*2], tree[lv-1][idx*2
> 44 }
> 45
> 46 Node QueryRec(int s, int e, int lv, int idx, int stride)
> 47 {
> 48 const int myL = stride*idx;
> 49 const int myR = stride*(idx+1);
> 50 if( e<=myL || myR<=s )
> 51 return Node::Zero();
> 52 if( s<=myL && myR<=e )
> 53 return tree[lv][idx];
> 54 return Node::Concat(QueryRec(s,e,lv-1,idx*2,stride/2),
> 55 QueryRec(s,e,lv-1,idx*2+1,stride/2));
> 56 }
> 57
> 58 void SetRec(int s, int e, const Node& n, int lv, int idx, int stride)
> 59 {
> 60 const int myL = stride*idx;
> 61 const int myR = stride*(idx+1);
> 62 if( e<=myL || myR<=s )
> 63 return;
> 64 if( stride == 1 ) {
> 65 tree[lv][idx] = n;
> 66 } else {
> 67 SetRec(s,e,n,lv-1,idx*2,stride/2);
> 68 SetRec(s,e,n,lv-1,idx*2+1,stride/2);
> 69 CalcMidNode(lv, idx);
> 70 }
> 71 }
> 72
> 73 vector< vector<Node> > tree;
> 74 };
> 75
> 76 struct Node
> 77 {
> 78 double sum;
> 79 double maxLeft;
> 80 double maxRight;
> 81 double maxSum;
> 82 static Node Zero()
> 83 {
> 84 Node c = {0, 0, 0, 0};
> 85 return c;
> 86 }
> 87 static Node One(double v)
> 88 {
> 89 Node c = {v, max(0.0,v), max(0.0,v), max(0.0,v)};
> 90 return c;
> 91 }
> 92 static Node Concat(const Node& l, const Node& r)
> 93 {
> 94 Node c = {
> 95 l.sum + r.sum,
> 96 max(l.maxLeft, l.sum+r.maxLeft),
> 97 max(l.maxRight+r.sum, r.maxRight),
> 98 max(max(l.maxSum, r.maxSum), l.maxRight+r.maxLeft),
> 99 };
> 100 return c;
> 101 }
> 102 };
> 103
> 104 /*
9 class SegmentTree 105 class SegmentTree
10 { 106 {
11 // --- DATA FOR EACH NODE --- 107 // --- DATA FOR EACH NODE ---
12 struct Node 108 struct Node
13 { 109 {
14 int sum; 110 int sum;
15 int maxLeft; 111 int maxLeft;
................................................................................................................................................................................
104 tree[lv-1][idx*2].switched ^= me; 200 tree[lv-1][idx*2].switched ^= me;
105 tree[lv-1][idx*2+1].switched ^= me; 201 tree[lv-1][idx*2+1].switched ^= me;
106 SwitchRec(Stride/2, lv-1, idx*2, Raw_L, Raw_R); 202 SwitchRec(Stride/2, lv-1, idx*2, Raw_L, Raw_R);
107 SwitchRec(Stride/2, lv-1, idx*2+1, Raw_L, Raw_R); 203 SwitchRec(Stride/2, lv-1, idx*2+1, Raw_L, Raw_R);
108 UpdateMidNode(lv, idx); 204 UpdateMidNode(lv, idx);
109 } 205 }
110 }; 206 };
> 207 */