Overview
| SHA1 Hash: | 58f56e668e79419936366b47c5c13ca5d7b53305 |
|---|---|
| Date: | 2012-02-18 03:50:50 |
| User: | kinaba |
| Comment: | Cleaned up segment tree for non-rannge-update case. |
| Timelines: | family | ancestors | descendants | both | trunk |
| Downloads: | Tarball | ZIP archive |
| Other Links: | files | file ages | manifest |
Tags And Properties
- branch=trunk inherited from [9165bd3629]
- sym-trunk inherited from [9165bd3629]
Changes
Modified lib/dataStructure/segmentTree.cpp from [d90f43e790c04822] to [0226be12935bcdf4].
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 */