diff options
| -rw-r--r-- | datastructures/RMQ.cpp | 27 | ||||
| -rw-r--r-- | datastructures/datastructures.tex | 10 |
2 files changed, 0 insertions, 37 deletions
diff --git a/datastructures/RMQ.cpp b/datastructures/RMQ.cpp deleted file mode 100644 index 401cca4..0000000 --- a/datastructures/RMQ.cpp +++ /dev/null @@ -1,27 +0,0 @@ -vector<int> values; -vector<vector<int>> rmq; - -int select(int a, int b) { - return values[a] <= values[b] ? a : b; -} - -void build() { - for(int i = 0, s = 1, ss = 1; s <= sz(values); ss=s, s*=2, i++) { - for(int l = 0; l + s <= sz(values); l++) { - if(i == 0) rmq[0][l] = l; - else { - int r = l + ss; - rmq[i][l] = select(rmq[i-1][l], rmq[i-1][r]]); -}}}} - -void init(const vector<int>& v) { - values = v; - rmq = vector<vector<int>>(__lg(sz(values))+1, vector<int>(sz(values))); - build(); -} - -int query(int l, int r) { - if(l >= r) return l; - int s = __lg(r-l); r = r - (1 << s); - return select(rmq[s][l],rmq[s][r]); -} diff --git a/datastructures/datastructures.tex b/datastructures/datastructures.tex index 4139219..61f04ba 100644 --- a/datastructures/datastructures.tex +++ b/datastructures/datastructures.tex @@ -122,16 +122,6 @@ \sourcecode{datastructures/stlHashMap.cpp} \end{algorithm} - - -\begin{algorithm}[optional]{Range Minimum Query} - \begin{methods} - \method{init}{baut Struktur auf}{n\*\log(n)} - \method{query}{Index des Minimums in [l, r)}{1} - \end{methods} - \sourcecode{datastructures/RMQ.cpp} -\end{algorithm} - \begin{algorithm}[optional]{Erste unbenutzte natürliche Zahl} \begin{methods} \method{get\_first\_unused}{findet kleinste unbenutzte Zahl}{\log(n)} |