aboutsummaryrefslogtreecommitdiff
path: root/Data Structures
diff options
context:
space:
mode:
authorTa180m2020-04-27 13:04:10 -0500
committerTa180m2020-04-27 13:04:10 -0500
commit125f34046c5b131b7fed3ee0a0190c33a3072020 (patch)
tree15db6b60bb398eb15e2377d0874e3d028c7bce35 /Data Structures
parent5faf4e7142044c5368549dee279bf0e3b2fd6a67 (diff)
Update segment_tree_v3.cpp
Diffstat (limited to 'Data Structures')
-rw-r--r--Data Structures/segment_tree_v3.cpp13
1 files changed, 11 insertions, 2 deletions
diff --git a/Data Structures/segment_tree_v3.cpp b/Data Structures/segment_tree_v3.cpp
index 2d29ff2..6308b9a 100644
--- a/Data Structures/segment_tree_v3.cpp
+++ b/Data Structures/segment_tree_v3.cpp
@@ -5,9 +5,18 @@ inline void push(int l, int r, int n) {
if (l != r) tmp[n << 1] += tmp[n], tmp[n << 1 | 1] += tmp[n];
tmp[n] = 0;
}
+void update(int x, T v, int l = 0, int r = -1, int n = 1) {
+ if (r == -1) r = 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]);
+ }
+}
void update(int a, int b, int v, int l = 0, int r = -1, int n = 1) {
if (r == -1) r = N - 1;
- if (tmp[n]) push(l, r, n);
+ push(l, r, n);
if (l > b || r < a) return;
if (l >= a && r <= b) {
tmp[n] += v;
@@ -22,7 +31,7 @@ void update(int a, int b, int v, int l = 0, int r = -1, int n = 1) {
int query(int a, int b, int l = 0, int r = -1, int n = 1) {
if (r == -1) r = N - 1;
if (a > b || l > b || r < a) return 0;
- if (tmp[n]) push(l, r, n);
+ push(l, r, n);
if (l >= a && r <= b) return seg[n];
int m = (l + r) >> 1;
return pull(query(a, b, l, m, n << 1), query(a, b, m + 1, r, n << 1 | 1));