diff options
Diffstat (limited to 'datastructures')
| -rw-r--r-- | datastructures/RMQ.cpp | 2 | ||||
| -rw-r--r-- | datastructures/datastructures.tex | 4 | ||||
| -rw-r--r-- | datastructures/fenwickTree.cpp | 21 |
3 files changed, 27 insertions, 0 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)); } +} + |