Create dynamic_segment_tree.cpp

1 files changed, 25 insertions, 0 deletions

diff --git a/Data Structures/dynamic_segment_tree.cpp b/Data Structures/dynamic_segment_tree.cpp
new file mode 100644
index 0000000..3ef368b
--- /dev/null
+++ b/Data Structures/dynamic_segment_tree.cpp
@@ -0,0 +1,25 @@
+struct node {
+	int val;
+	node* c[2];
+	node() {
+		val = 0;
+		c[0] = c[1] = 0;
+	}
+	node* get_c(int i) {
+		return (!c[i] ? c[i] = new node : c[i]);
+	}
+	void update(int x, long long v, int l, int r) {
+		if (l == r) val += v;
+		else {
+			int m = (l + r) >> 1;
+			x <= m ? get_c(0)->update(x, v, l, m) : get_c(1)->update(x, v, m + 1, r);
+			val = (c[0] ? c[0]->val : 0) + (c[1] ? c[1]->val : 0);
+		}
+	}
+	long long query(int a, int b, int l, int r) {
+		if (a > r || b < l) return 0;
+		if (a <= l && b >= r) return val;
+		int m = (l + r) >> 1;
+		return (c[0] ? c[0]->query(a, b, l, m) : 0) + (c[1] ? c[1]->query(a, b, m + 1, r) : 0);
+	}
+};