diff options
Diffstat (limited to 'datastructures')
| -rw-r--r-- | datastructures/RMQ.cpp | 11 | ||||
| -rw-r--r-- | datastructures/datastructures.tex | 4 | ||||
| -rw-r--r-- | datastructures/fenwickTree.cpp | 8 | ||||
| -rw-r--r-- | datastructures/stlTree.cpp | 2 |
4 files changed, 11 insertions, 14 deletions
diff --git a/datastructures/RMQ.cpp b/datastructures/RMQ.cpp index 3c3f44c..8e6a33f 100644 --- a/datastructures/RMQ.cpp +++ b/datastructures/RMQ.cpp @@ -1,7 +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)) +// Baut Struktur auf. 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++) { @@ -9,12 +9,9 @@ void initRMQ() { else { int r = l + ss; rmq[i][l] = (data[rmq[i-1][l]] <= data[rmq[i-1][r]] ? rmq[i-1][l] : rmq[i-1][r]); - } - } - } -} -//returns index of minimum! [l, r) -//Runtime: O(1) +}}}} + +// Gibt den Index des Minimums im Intervall [l,r) zurück. 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 7b5b076..4267090 100644 --- a/datastructures/datastructures.tex +++ b/datastructures/datastructures.tex @@ -5,8 +5,8 @@ \subsection{Segmentbaum} \lstinputlisting{datastructures/segmentTree.cpp} -\lstinline{update()} kann so umgeschrieben werden, dass ganze Intervalle geändert werden. -Dazu muss ein Offset in den inneren Knoten des Baums gespeichert werden. +Mit \lstinline{update()} können ganze Intervalle geändert werden. +Dazu: Offset in den inneren Knoten des Baums speichern. \subsection{Fenwick Tree} \lstinputlisting{datastructures/fenwickTree.cpp} diff --git a/datastructures/fenwickTree.cpp b/datastructures/fenwickTree.cpp index cd30329..86b1138 100644 --- a/datastructures/fenwickTree.cpp +++ b/datastructures/fenwickTree.cpp @@ -1,19 +1,19 @@ -vector<int> FT; //Fenwick-Tree +vector<int> FT; // Fenwick-Tree int n; -//Adds val to index i. Time Complexity O(log(n)) +// Addiert val zum Element an Index i. O(log(n)). void updateFT(int i, int val) { i++; while(i <= n) { FT[i] += val; i += (i & (-i)); } } -//Build an Fenwick-Tree over an array a. Time Complexity: O(n*log(n)) +// Baut Baum auf. O(n*log(n)). void 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)) +// Präfix-Summe über das Intervall [0..i]. O(log(n)). int prefix_sum(int i) { int sum = 0; i++; while(i > 0) { sum += FT[i]; i -= (i & (-i)); } diff --git a/datastructures/stlTree.cpp b/datastructures/stlTree.cpp index 73472a7..bdbeae3 100644 --- a/datastructures/stlTree.cpp +++ b/datastructures/stlTree.cpp @@ -7,6 +7,6 @@ int main() { Tree X; for (int i = 1; i <= 16; i <<= 1) X.insert(i); // {1, 2, 4, 8, 16} cout << *X.find_by_order(3) << endl; // => 8 - cout << X.order_of_key(10) << endl; // => 4 = successor of 10 = min i such that X[i] >= 10 + cout << X.order_of_key(10) << endl; // => 4 = Nachfolger von 10 = minimales i, sodass X[i] >= 10 return 0; }
\ No newline at end of file |