1 files changed, 46 insertions, 0 deletions
diff --git a/segmenttree.c b/segmenttree.c
index e69de29..1bf0fcd 100644
--- a/segmenttree.c
+++ b/segmenttree.c
@@ -0,0 +1,46 @@
+struct SegmentTree {
+	int N;
+	int * seg;
+}
+
+// Build segment tree
+void Build(int l, int r, int n) {
+	if (l == r) {
+	
+	}
+	int m = l + r >> 1;
+	Build(l, m, n << 1);
+	Build(m + 1, r, n << 1 | 1);
+	seg[n] = seg[n << 1] + seg[n << 1 | 1];
+}
+
+// Update value at index x
+void Update(int x, int v, int l, int r, int n) {
+	if (l == r) {
+		seg[n] += v;
+		return;
+	}
+	int m = l + r >> 1;
+	if (x <= m) {
+		Update(x, v, l, m, n<<1);
+	}
+	else {
+		Update(x, v, m+1, r, n<<1|1);
+	}
+	seg[n] = seg[n << 1] + seg[n << 1 | 1];
+}
+
+// Find element with prefix sum v
+int Query(int v, int l, int r, int n) {
+	if (l == r) {
+		return s.seg[n], l;
+	}
+	int m = l + r >> 1;
+	if (seg[n << 1] >= v) {
+		return Query(v, l, m, n << 1);
+	}
+	else {
+		return Query(v - s.seg[n << 1], m + 1, r, n << 1 | 1);
+	}
+}
+