Add Fenwick-Tree to section datastructures

3 files changed, 25 insertions, 0 deletions

diff --git a/datastructures/datastructures.tex b/datastructures/datastructures.tex
index 7edb390..7b5b076 100644
--- a/datastructures/datastructures.tex
+++ b/datastructures/datastructures.tex
@@ -8,6 +8,10 @@
 \lstinline{update()} kann so umgeschrieben werden, dass ganze Intervalle geändert werden.
 Dazu muss ein Offset in den inneren Knoten des Baums gespeichert werden.
 
+\subsection{Fenwick Tree}
+\lstinputlisting{datastructures/fenwickTree.cpp}
+
+
 \subsection{Range Minimum Query}
 \lstinputlisting{datastructures/RMQ.cpp}
 
diff --git a/datastructures/fenwickTree.cpp b/datastructures/fenwickTree.cpp
new file mode 100644
index 0000000..02be7d4
--- /dev/null
+++ b/datastructures/fenwickTree.cpp
@@ -0,0 +1,21 @@
+vector<int> FT; //Fenwick-Tree
+
+//Build an Fenwick-Tree over an array a. Time Complexity: O(n*log(n))
+buildFenwickTree(vector<int>& a) {
+  n = a.size();
+  FT.assign(n+1,0);
+  for(int i = 0; i < n; i++)  updateFT(i,a[i]);
+}
+
+//Prefix-Sum of intervall [0..i]. Time Complexity: O(log(n))
+int prefix_sum(int i) {
+  int sum = 0; i++;
+  while(i > 0) { sum += FT[i]; i -= (i & (-i)); }	
+  return sum;
+}
+
+//Adds val to index i. Time Complexity O(log(n))
+void updateFT(int i, int val) {
+	i++; while(i <= n) { FT[i] += val; i += (i & (-i)); }
+}
+	
diff --git a/tcr.pdf b/tcr.pdf
index f80ccd7..b5a2052 100644
--- a/tcr.pdf
+++ b/tcr.pdf