From 5ab8a5088b729a9953b8dff1b2a985dc8fb2098b Mon Sep 17 00:00:00 2001
From: mzuenni <michi.zuendorf@gmail.com>
Date: Mon, 27 Jun 2022 17:19:28 +0200
Subject: updated tcr

---
 datastructures/fenwickTree2.cpp | 21 +++++++++++++++++++++
 1 file changed, 21 insertions(+)
 create mode 100644 datastructures/fenwickTree2.cpp

(limited to 'datastructures/fenwickTree2.cpp')

diff --git a/datastructures/fenwickTree2.cpp b/datastructures/fenwickTree2.cpp
new file mode 100644
index 0000000..dfd5dc5
--- /dev/null
+++ b/datastructures/fenwickTree2.cpp
@@ -0,0 +1,21 @@
+vector<ll> add, mul;
+
+void update(int l, int r, ll val) {
+	for (int tl = l + 1; tl < sz(add); tl += tl&(-tl))
+		add[tl] += val, mul[tl] -= val * l;
+	for (int tr = r + 1; tr < sz(add); tr += tr&(-tr))
+		add[tr] -= val, mul[tr] += val * r; 
+}
+
+void init(vector<ll>& v) {
+	mul.assign(sz(v) + 1,0);
+	add.assign(sz(v) + 1,0);
+	for(int i = 0; i < sz(v); i++) update(i, i + 1, v[i]);
+}
+
+ll prefix_sum (int i) {
+	ll res = 0; i++;
+	for (int ti = i; ti > 0; ti -= ti&(-ti))
+		res += add[ti] * i + mul[ti];
+	return res;
+}
-- 
cgit v1.2.3