aboutsummaryrefslogtreecommitdiff
path: root/Data Structures
diff options
context:
space:
mode:
authorAnthony Wang2020-09-21 12:49:18 -0500
committerAnthony Wang2020-09-21 12:49:18 -0500
commitd79f8f412ce62129f724df17fe7c13827499e01b (patch)
tree11be807eb43fc2dd4e1b68391385890fb9e889fd /Data Structures
parent57c74f6551b098e0d87cbe75b2a03ed0147995a6 (diff)
More cleanup
Diffstat (limited to 'Data Structures')
-rw-r--r--Data Structures/segment_tree.cpp35
1 files changed, 13 insertions, 22 deletions
diff --git a/Data Structures/segment_tree.cpp b/Data Structures/segment_tree.cpp
index b7c6e05..1fe409f 100644
--- a/Data Structures/segment_tree.cpp
+++ b/Data Structures/segment_tree.cpp
@@ -7,39 +7,30 @@ template<typename T> struct seg_tree {
tmp[n] = 0;
}
void build(T v, int l = 0, int r = MX-1, int n = 1) {
- if (l == r) seg[n] = v;
- else {
- int m = (l+r)>>1;
- build(v, l, m, n<<1), build(v, m+1, r, n<<1|1);
- seg[n] = pull(seg[n<<1], seg[n<<1|1]);
- }
+ if (l == r) { seg[n] = v; return; }
+ int m = l+r>>1;
+ build(v, l, m, n<<1), build(v, m+1, r, n<<1|1);
+ seg[n] = pull(seg[n<<1], seg[n<<1|1]);
}
void update(int x, T v, int l = 0, int r = MX-1, int n = 1) {
- if (l == r) seg[n] += v;
- else {
- int m = (l+r)>>1;
- x <= m ? update(x, v, l, m, n<<1) : update(x, v, m+1, r, n<<1|1);
- seg[n] = pull(seg[n<<1], seg[n<<1|1]);
- }
+ if (l == r) { seg[n] += v; return; }
+ int m = l+r>>1;
+ x <= m ? update(x, v, l, m, n<<1) : update(x, v, m+1, r, n<<1|1);
+ seg[n] = pull(seg[n<<1], seg[n<<1|1]);
}
void update(int a, int b, T v, int l = 0, int r = MX-1, int n = 1) {
push(l, r, n);
if (l > r || l > b || r < a) return;
- if (l >= a && r <= b) {
- tmp[n] += v;
- push(l, r, n);
- }
- else {
- int m = (l+r)>>1;
- update(a, b, v, l, m, n<<1), update(a, b, v, m+1, r, n<<1|1);
- seg[n] = pull(seg[n<<1], seg[n<<1|1]);
- }
+ if (l >= a && r <= b) { tmp[n] += v, push(l, r, n); return; }
+ int m = l+r>>1;
+ update(a, b, v, l, m, n<<1), update(a, b, v, m+1, r, n<<1|1);
+ seg[n] = pull(seg[n<<1], seg[n<<1|1]);
}
T query(int a, int b, int l = 0, int r = MX-1, int n = 1) {
if (a > b || l > b || r < a) return 0;
push(l, r, n);
if (l >= a && r <= b) return seg[n];
- int m = (l+r)>>1;
+ int m = l+r>>1;
return pull(query(a, b, l, m, n<<1), query(a, b, m+1, r, n<<1|1));
}
};