summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--TestMakefile1
-rw-r--r--datastructures/datastructures.tex27
-rw-r--r--datastructures/test/waveletTree.cpp38
-rw-r--r--datastructures/waveletTree.cpp26
4 files changed, 63 insertions, 29 deletions
diff --git a/TestMakefile b/TestMakefile
index 5c46856..59a902f 100644
--- a/TestMakefile
+++ b/TestMakefile
@@ -10,6 +10,7 @@ TESTS := \
$(call with-defines-subsets,datastructures/test/segmentTree.SEGTREE_FIRST_NEG,SEGTREE_INIT_DEFAULT) \
$(call with-defines-subsets,datastructures/test/lazyPropagation,SEGTREE_FIRST_NEG SEGTREE_INIT_DEFAULT) \
$(call with-defines-subsets,datastructures/test/lazyPropagation.SEGTREE_MAX,SEGTREE_INIT_DEFAULT) \
+ datastructures/test/waveletTree \
datastructures/test/fenwickTree \
datastructures/test/fenwickTree2 \
datastructures/test/monotonicConvexHull \
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;}
};
generated by cgit v1.2.3 (git 2.39.1) at 2025-12-23 18:36:11 +0000