1 files changed, 15 insertions, 0 deletions
diff --git a/content/datastructures/fenwickTree.cpp b/content/datastructures/fenwickTree.cpp
new file mode 100644
index 0000000..7013613
--- /dev/null
+++ b/content/datastructures/fenwickTree.cpp
@@ -0,0 +1,15 @@
+vector<ll> tree;
+
+void update(int i, ll val) {
+	for (i++; i < ssize(tree); i += i & -i) tree[i] += val;
+}
+
+void init(int n) {
+	tree.assign(n + 1, 0);
+}
+
+ll prefix_sum(int i) {
+	ll sum = 0;
+	for (; i > 0; i &= i-1) sum += tree[i];
+	return sum;
+}