Merge in Fenwick Tree

6 files changed, 30 insertions, 1 deletions

diff --git a/datastructures/RMQ.cpp b/datastructures/RMQ.cpp
index 9047b33..3c3f44c 100644
--- a/datastructures/RMQ.cpp
+++ b/datastructures/RMQ.cpp
@@ -1,6 +1,7 @@
 vector<int> data(RMQ_SIZE);
 vector<vector<int>> rmq(floor(log2(RMQ_SIZE)) + 1, vector<int>(RMQ_SIZE));
 
+//Runtime: O(n*log(n))
 void initRMQ() {
 	for(int i = 0, s = 1, ss = 1; s <= RMQ_SIZE; ss=s, s*=2, i++) {
 		for(int l = 0; l + s <= RMQ_SIZE; l++) {
@@ -13,6 +14,7 @@ void initRMQ() {
 	}
 }
 //returns index of minimum! [l, r)
+//Runtime: O(1)
 int queryRMQ(int l, int r) {
 	if(l >= r) return l;
 	int s = floor(log2(r-l)); r = r - (1 << s);
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/graph/LCA.cpp b/graph/LCA.cpp
index b4e6bdd..da3b5f7 100644
--- a/graph/LCA.cpp
+++ b/graph/LCA.cpp
@@ -2,6 +2,7 @@
 vector<int> visited(2*MAX_N), first(MAX_N, 2*MAX_N), depth(2*MAX_N);
 vector<vector<int>> graph(MAX_N);
 
+//Runtime: O(n)
 void initLCA(int gi, int d, int &c) {
 	visited[c] = gi, depth[c] = d, first[gi] = min(c, first[gi]), c++;
 	for(int gn : graph[gi]) {
@@ -10,6 +11,7 @@ void initLCA(int gi, int d, int &c) {
 	}
 }
 //[a, b]
+//Runtime: O(1)
 int getLCA(int a, int b) {
 	return visited[queryRMQ(min(first[a], first[b]), max(first[a], first[b]))];
 }
diff --git a/math/nimm.cpp b/math/nimm.cpp
index 3da6ca1..837a2ad 100644
--- a/math/nimm.cpp
+++ b/math/nimm.cpp
@@ -1,4 +1,4 @@
-#Most important function!!
+#Most important function!!!11elf
 bool WinNimm(vector<int> game) {
 	int result = 0;
 	for(int s: game) result ^= s;
diff --git a/tcr.pdf b/tcr.pdf
index e9b89a5..633caef 100644
--- a/tcr.pdf
+++ b/tcr.pdf