diff options
author | Anthony Wang | 2020-09-21 12:49:18 -0500 |
---|---|---|
committer | Anthony Wang | 2020-09-21 12:49:18 -0500 |
commit | d79f8f412ce62129f724df17fe7c13827499e01b (patch) | |
tree | 11be807eb43fc2dd4e1b68391385890fb9e889fd /Data Structures | |
parent | 57c74f6551b098e0d87cbe75b2a03ed0147995a6 (diff) |
More cleanup
Diffstat (limited to 'Data Structures')
-rw-r--r-- | Data Structures/segment_tree.cpp | 35 |
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)); } }; |