diff options
Diffstat (limited to 'datastructures')
| -rw-r--r-- | datastructures/datastructures.tex | 27 | ||||
| -rw-r--r-- | datastructures/test/waveletTree.cpp | 38 | ||||
| -rw-r--r-- | datastructures/waveletTree.cpp | 26 |
3 files changed, 62 insertions, 29 deletions
diff --git a/datastructures/datastructures.tex b/datastructures/datastructures.tex index ffa4c40..43d6dd8 100644 --- a/datastructures/datastructures.tex +++ b/datastructures/datastructures.tex @@ -3,38 +3,41 @@ \begin{algorithm}{Segmentbaum} \begin{methods} \method{SegTree}{baut den Baum auf}{n} - \method{query}{findet Summe über [l, r)}{\log(n)} + \method{query}{findet Summe über $[l, r)$}{\log(n)} \method{update}{ändert einen Wert}{\log(n)} \end{methods} \sourcecode{datastructures/segmentTree.cpp} \subsubsection{Lazy Propagation} Assignment modifications, sum queries \\ - \method{lower\_bound}{erster Index in [l, r) $\geq$ x (erfordert max-combine)}{\log(n)} + \method{lower\_bound}{erster Index in $[l, r) \geq x$ (erfordert max-combine)}{\log(n)} \sourcecode{datastructures/lazyPropagation.cpp} \end{algorithm} \begin{algorithm}{Wavelet Tree} \begin{methods} - \method{Constructor}{baut den Baum auf}{n\*\log(n)} - \method{kth}{sort $[l, r)[k]$}{\log(n)} - \method{countSmaller}{Anzahl elemente in $[l, r)$ kleiner als $k$}{\log(n)} + \method{WaveletTree}{baut den Baum auf}{n\*\log(A)} + \method{kth}{sort $[l, r)[k]$}{\log(A)} + \method{countSmaller}{Anzahl elemente in $[l, r)$ kleiner als $k$}{\log(A)} \end{methods} + $A$ ist die Gr\"o\ss e des Eingabebereichs, d.h. + $\mathit{max} - \mathit{min}$. \sourcecode{datastructures/waveletTree.cpp} \end{algorithm} +\columnbreak \begin{algorithm}{Fenwick Tree} \begin{methods} \method{init}{baut den Baum auf}{n\*\log(n)} - \method{prefix\_sum}{summe von [0, i)}{\log(n)} + \method{prefix\_sum}{summe von $[0, i)$}{\log(n)} \method{update}{addiert ein Delta zu einem Element}{\log(n)} \end{methods} \sourcecode{datastructures/fenwickTree.cpp} \begin{methods} \method{init}{baut den Baum auf}{n\*\log(n)} - \method{prefix\_sum}{summe von [0, i)}{\log(n)} - \method{update}{addiert ein Delta zu allen Elementen [l, r)}{\log(n)} + \method{prefix\_sum}{summe von $[0, i)$}{\log(n)} + \method{update}{addiert ein Delta zu allen Elementen $[l, r)$}{\log(n)} \end{methods} \sourcecode{datastructures/fenwickTree2.cpp} \end{algorithm} @@ -46,7 +49,7 @@ \begin{algorithm}{(Implicit) Treap (Cartesian Tree)} \begin{methods} - \method{insert}{fügt wert $\mathit{val}$ an stelle $i$ ein (verschiebt alle Positionen >= $i$)}{\log(n)} + \method{insert}{fügt wert $\mathit{val}$ an stelle $i$ ein (verschiebt alle Positionen $\geq i$)}{\log(n)} \method{remove}{löscht werte $[i,i+\mathit{count})$}{\log(n)} \end{methods} \sourcecode{datastructures/treap2.cpp} @@ -55,7 +58,7 @@ \begin{algorithm}{Range Minimum Query} \begin{methods} \method{init}{baut Struktur auf}{n\*\log(n)} - \method{queryIdempotent}{Index des Minimums in [l, r)}{1} + \method{queryIdempotent}{Index des Minimums in $[l, r)$}{1} \end{methods} \begin{itemize} \item \code{better}-Funktion muss idempotent sein! @@ -66,7 +69,7 @@ \begin{algorithm}[optional]{Range Aggregate Query} \begin{methods} \method{init}{baut Struktur auf}{n\*\log(n)} - \method{query}{Aggregat über [l,r)}{1} + \method{query}{Aggregat über $[l,r)$}{1} \end{methods} \sourcecode{datastructures/sparseTableDisjoint.cpp} \end{algorithm} @@ -77,7 +80,7 @@ \begin{algorithm}{Link-Cut-Tree} \begin{methods} - \method{Constructor}{baut Wald auf}{n} + \method{LCT}{baut Wald auf}{n} \method{connected}{prüft ob zwei Knoten im selben Baum liegen}{\log(n)} \method{link}{fügt $\{x,y\}$ Kante ein}{\log(n)} \method{cut}{entfernt $\{x,y\}$ Kante}{\log(n)} diff --git a/datastructures/test/waveletTree.cpp b/datastructures/test/waveletTree.cpp new file mode 100644 index 0000000..c5da1d2 --- /dev/null +++ b/datastructures/test/waveletTree.cpp @@ -0,0 +1,38 @@ +#include "../waveletTree.cpp" + +void test(int n) { + vector<ll> values(n); + for (ll &x: values) x = util::randint(); + vector<ll> backup = values; + WaveletTree wave(values); + assert(values == backup); + for (int i = 0; i < n; i++) { + int l = util::randint(n+1); + int r = util::randint(n+1); + if (l > r) swap(l, r); + ll bound = util::randint(); + int res = 0; + for (ll x: values | views::take(r) | views::drop(l)) { + if (x < bound) res++; + } + assert(wave.countSmaller(l, r, bound) == res); + } + for (int i = 0; 5*i < n; i++) { + int l = util::randint(n); + int m = util::randint(n); + int r = util::randint(n); + if (l > m) swap(l, m); + if (m > r) swap(m, r); + if (l > m) swap(l, m); + r++; + int k = m-l; + vector<ll> part(values.begin()+l, values.begin()+r); + ranges::nth_element(part, part.begin() + k); + assert(wave.kth(l, r, k) == part[k]); + } +} + +int main() { + test(1000); + test(1); +} diff --git a/datastructures/waveletTree.cpp b/datastructures/waveletTree.cpp index 476658e..95ff207 100644 --- a/datastructures/waveletTree.cpp +++ b/datastructures/waveletTree.cpp @@ -1,25 +1,20 @@ struct WaveletTree { - using it = vector<ll>::iterator; - WaveletTree *ln = nullptr, *rn = nullptr; + unique_ptr<WaveletTree> ln, rn; vector<int> b = {0}; ll lo, hi; - WaveletTree(vector<ll> in) : WaveletTree(all(in)) {} - - WaveletTree(it from, it to) : // call above one - lo(*min_element(from, to)), hi(*max_element(from, to) + 1) { + WaveletTree(auto in) : lo(*ranges::min_element(in)), + hi(*ranges::max_element(in) + 1) { ll mid = (lo + hi) / 2; - auto f = [&](ll x) {return x < mid;}; - for (it c = from; c != to; c++) { - b.push_back(b.back() + f(*c)); - } + auto f = [&](ll x) { return x < mid; }; + for (ll x: in) b.push_back(b.back() + f(x)); if (lo + 1 >= hi) return; - it pivot = stable_partition(from, to, f); - ln = new WaveletTree(from, pivot); - rn = new WaveletTree(pivot, to); + auto right = ranges::stable_partition(in, f); + ln = make_unique<WaveletTree>( + ranges::subrange(begin(in), begin(right))); + rn = make_unique<WaveletTree>(right); } - // kth element in sort[l, r) all 0-indexed ll kth(int l, int r, int k) { if (l >= r || k >= r - l) return -1; if (lo + 1 >= hi) return lo; @@ -28,13 +23,10 @@ struct WaveletTree { else return rn->kth(l-b[l], r-b[r], k-inLeft); } - // count elements in[l, r) smaller than k int countSmaller(int l, int r, ll k) { if (l >= r || k <= lo) return 0; if (hi <= k) return r - l; return ln->countSmaller(b[l], b[r], k) + rn->countSmaller(l-b[l], r-b[r], k); } - - ~WaveletTree() {delete ln; delete rn;} }; |