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 2 // Segment tree
3 3 // in some general form
4 4 //
5 5 // Verified by
6 +// - Codeforces 107 C
6 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::Zero();
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+1]);
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 105 class SegmentTree
10 106 {
11 107 // --- DATA FOR EACH NODE ---
12 108 struct Node
13 109 {
14 110 int sum;
15 111 int maxLeft;
................................................................................
104 200 tree[lv-1][idx*2].switched ^= me;
105 201 tree[lv-1][idx*2+1].switched ^= me;
106 202 SwitchRec(Stride/2, lv-1, idx*2, Raw_L, Raw_R);
107 203 SwitchRec(Stride/2, lv-1, idx*2+1, Raw_L, Raw_R);
108 204 UpdateMidNode(lv, idx);
109 205 }
110 206 };
207 +*/