Adding Niklas Fenwick Tree Code.

2 files changed, 57 insertions, 0 deletions

diff --git a/datastructures/datastructures.tex b/datastructures/datastructures.tex
index 20dec7f..792fc93 100644
--- a/datastructures/datastructures.tex
+++ b/datastructures/datastructures.tex
@@ -10,6 +10,7 @@ Dazu: Offset in den inneren Knoten des Baums speichern.
 
 \subsection{Fenwick Tree}
 \lstinputlisting{datastructures/fenwickTree.cpp}
+\lstinputlisting{datastructures/fenwickTreeNiklas.cpp}
 
 \subsection{Range Minimum Query}
 \lstinputlisting{datastructures/RMQ.cpp}
diff --git a/datastructures/fenwickTreeNiklas.cpp b/datastructures/fenwickTreeNiklas.cpp
new file mode 100644
index 0000000..032f74c
--- /dev/null
+++ b/datastructures/fenwickTreeNiklas.cpp
@@ -0,0 +1,56 @@
+const int n = 10000; // ALL INDICES START AT 1 WITH THIS CODE!!
+
+// mode 1: update indices, read prefixes
+void update_idx(int tree[], int i, int val) { // v[i] += val
+  for (; i <= n; i += i & -i) tree[i] += val;
+}
+int read_prefix(int tree[], int i) { // get sum v[1..i]
+  int sum = 0;
+  for (; i > 0; i -= i & -i) sum += tree[i];
+  return sum;
+}
+int kth(int k) { // find kth element in tree (1-based index)
+  int ans = 0;
+  for (int i = maxl; i >= 0; --i) // maxl = largest i s.t. (1<<i) <= n
+    if (ans + (1<<i) <= n && tree[ans + (1<<i)] < k) {
+      ans += 1<<i;
+      k -= tree[ans];
+    }
+  return ans+1;
+}
+
+// mode 2: update prefixes, read indices
+void update_prefix(int tree[], int i, int val) { // v[1..i] += val
+  for (; i > 0; i -= i & -i) tree[i] += val;
+}
+int read_idx(int tree[], int i) { // get v[i]
+  int sum = 0;
+  for (; i <= n; i += i & -i) sum += tree[i];
+  return sum;
+}
+
+// mode 3: range-update range-query
+const int maxn = 100100;
+int n;
+ll mul[maxn], add[maxn];
+
+void update_idx(ll tree[], int x, ll val) {
+  for (int i = x; i <= n; i += i & -i) tree[i] += val;
+}
+void update_prefix(int x, ll val) { // v[x] += val
+  update_idx(mul, 1, val);
+  update_idx(mul, x + 1, -val);
+  update_idx(add, x + 1, x * val);
+}
+ll read_prefix(int x) { // get sum v[1..x]
+  ll a = 0, b = 0;
+  for (int i = x; i > 0; i -= i & -i) a += mul[i], b += add[i];
+  return a * x + b;
+}
+void update_range(int l, int r, ll val) { // v[l..r] += val
+  update_prefix(l - 1, -val);
+  update_prefix(r, val);
+}
+ll read_range(int l, int r) { // get sum v[l..r]
+  return read_prefix(r) - read_prefix(l - 1);
+}