aboutsummaryrefslogtreecommitdiff
path: root/segmenttree.c
diff options
context:
space:
mode:
authorAnthony Wang2022-04-19 08:23:47 -0500
committerAnthony Wang2022-04-19 08:23:47 -0500
commit74b018bf1c5b89a77447d25b7bbdb1ba7cbc5dd4 (patch)
tree16ee602d816f3e3af6926daa731170fab80357ee /segmenttree.c
parent530da23dfca6c39ed08f2fcd3a106c345c89baeb (diff)
Implement C arg parsing with getopt_long
Diffstat (limited to 'segmenttree.c')
-rw-r--r--segmenttree.c46
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);
+ }
+}
+