diff options
Diffstat (limited to 'datastructures')
29 files changed, 697 insertions, 206 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 1ccefaa..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! @@ -63,13 +66,21 @@ \sourcecode{datastructures/sparseTable.cpp} \end{algorithm} +\begin{algorithm}[optional]{Range Aggregate Query} + \begin{methods} + \method{init}{baut Struktur auf}{n\*\log(n)} + \method{query}{Aggregat über $[l,r)$}{1} + \end{methods} + \sourcecode{datastructures/sparseTableDisjoint.cpp} +\end{algorithm} + \begin{algorithm}{STL-Bitset} \sourcecode{datastructures/bitset.cpp} \end{algorithm} \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)} @@ -79,23 +90,35 @@ \end{methods} \sourcecode{datastructures/LCT.cpp} \end{algorithm} -\clearpage - -\begin{algorithm}{Lichao} - \sourcecode{datastructures/lichao.cpp} -\end{algorithm} +\columnbreak \begin{algorithm}{Policy Based Data Structures} - \textbf{Wichtig:} Verwende \code{p.swap(p2)} anstatt \code{swap(p, p2)}! - \sourcecode{datastructures/stlPriorityQueue.cpp} - \columnbreak \sourcecode{datastructures/pbds.cpp} \end{algorithm} -\begin{algorithm}{Lower/Upper Envelope (Convex Hull Optimization)} - Um aus einem lower envelope einen upper envelope zu machen (oder umgekehrt), einfach beim Einfügen der Geraden $m$ und $b$ negieren. +\begin{algorithm}{Lower Envelope (Convex Hull Optimization)} + Um aus einem Lower Envelope einen Upper Envelope zu machen (oder + umgekehrt), einfach beim Einfügen der Geraden $m$ und $b$ negieren. + \subsubsection{Monotonic} + \begin{methods} + \method{add}{add line $mx + b$, $m$ is decreasing}{1} + \method{query}{minimum value at $x$, $x$ is increasing}{1} + \end{methods} \sourcecode{datastructures/monotonicConvexHull.cpp} + \subsubsection{Dynamic} + \begin{methods} + \method{add}{add line $mx + b$}{\log(n)} + \method{query}{minimum value at $x$}{\log(n)} + \end{methods} \sourcecode{datastructures/dynamicConvexHull.cpp} + \subsubsection{Li Chao Tree} + Every pair of functions has at most one intersection. + + \begin{methods} + \method{insert}{add function}{\log(|xs|)} + \method{query}{minimum value at $x$, $x \in xs$}{\log(|xs|)} + \end{methods} + \sourcecode{datastructures/lichao.cpp} \end{algorithm} \begin{algorithm}{Union-Find} @@ -107,6 +130,17 @@ \end{methods} \sourcecode{datastructures/unionFind.cpp} \end{algorithm} + +\begin{algorithm}[optional]{Union-Find with size} + \begin{methods} + \method{init}{legt $n$ einzelne Unions an}{n} + \method{findSet}{findet den Repräsentanten}{\log(n)} + \method{unionSets}{vereint 2 Mengen}{\log(n)} + \method{getSize}{zählt Elemente in Menge, die $i$ enthält}{\log(n)} + \method{m\*findSet + n\*unionSets}{Folge von Befehlen}{n+m\*\alpha(n)} + \end{methods} + \sourcecode{datastructures/unionFind2.cpp} +\end{algorithm} \columnbreak \begin{algorithm}{Persistent} @@ -119,14 +153,6 @@ \sourcecode{datastructures/persistentArray.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)} diff --git a/datastructures/dynamicConvexHull.cpp b/datastructures/dynamicConvexHull.cpp index d669847..2bd67a6 100644 --- a/datastructures/dynamicConvexHull.cpp +++ b/datastructures/dynamicConvexHull.cpp @@ -19,13 +19,11 @@ struct HullDynamic : multiset<Line, less<>> { auto x = insert({m, b, 0}); while (isect(x, next(x))) erase(next(x)); if (x != begin()) { - x--; - if (isect(x, next(x))) { - erase(next(x)); - isect(x, next(x)); - }} + --x; + while (isect(x, next(x))) erase(next(x)); + } while (x != begin() && prev(x)->p >= x->p) { - x--; + --x; isect(x, erase(next(x))); }} diff --git a/datastructures/fenwickTree.cpp b/datastructures/fenwickTree.cpp index cac3cf8..8c73b78 100644 --- a/datastructures/fenwickTree.cpp +++ b/datastructures/fenwickTree.cpp @@ -1,15 +1,15 @@ vector<ll> tree; void update(int i, ll val) { - for (i++; i < sz(tree); i += (i & (-i))) tree[i] += val; + for (i++; i < ssize(tree); i += i & -i) tree[i] += val; } void init(int n) { - tree.assign(n + 1,0); + tree.assign(n + 1, 0); } ll prefix_sum(int i) { ll sum = 0; - for (i++; i > 0; i -= (i & (-i))) sum += tree[i]; + for (; i > 0; i -= i & -i) sum += tree[i]; return sum; } diff --git a/datastructures/fenwickTree2.cpp b/datastructures/fenwickTree2.cpp index ff87e2e..086e785 100644 --- a/datastructures/fenwickTree2.cpp +++ b/datastructures/fenwickTree2.cpp @@ -1,21 +1,21 @@ vector<ll> add, mul; void update(int l, int r, ll val) { - for (int tl = l + 1; tl < sz(add); tl += tl&(-tl)) + for (int tl = l + 1; tl < ssize(add); tl += tl & -tl) add[tl] += val, mul[tl] -= val * l; - for (int tr = r + 1; tr < sz(add); tr += tr&(-tr)) + for (int tr = r + 1; tr < ssize(add); tr += tr & -tr) add[tr] -= val, mul[tr] += val * r; } void init(vector<ll>& v) { - mul.assign(sz(v) + 1,0); - add.assign(sz(v) + 1,0); - for(int i = 0; i < sz(v); i++) update(i, i + 1, v[i]); + mul.assign(size(v) + 1, 0); + add.assign(size(v) + 1, 0); + for(int i = 0; i < ssize(v); i++) update(i, i + 1, v[i]); } -ll prefix_sum (int i) { - ll res = 0; i++; - for (int ti = i; ti > 0; ti -= ti&(-ti)) +ll prefix_sum(int i) { + ll res = 0; + for (int ti = i; ti > 0; ti -= ti & -ti) res += add[ti] * i + mul[ti]; return res; } diff --git a/datastructures/lazyPropagation.cpp b/datastructures/lazyPropagation.cpp index 7af1a6a..3d3ea6b 100644 --- a/datastructures/lazyPropagation.cpp +++ b/datastructures/lazyPropagation.cpp @@ -1,21 +1,22 @@ struct SegTree { using T = ll; using U = ll; - int n, h; static constexpr T E = 0; // Neutral element for combine static constexpr U UF = 0; // Unused value by updates + int n; vector<T> tree; vector<U> lazy; + int h; vector<ll> k; // size of segments (optional) - SegTree(const vector<T>& a) : n(sz(a) + 1), tree(2 * n, E), + SegTree(const vector<T>& a) : n(ssize(a) + 1), tree(2 * n), //SegTree(int size, T def = E) : n(size + 1), tree(2 * n, def), - h(__lg(2 * n)), lazy(n, UF), k(2 * n, 1) { - copy(all(a), tree.begin() + n); + lazy(n, UF), h(__lg(2 * n)), k(2 * n, 1) { + ranges::copy(a, tree.begin() + n); for (int i = n - 1; i > 0; i--) { k[i] = 2 * k[2 * i]; tree[i] = comb(tree[2 * i], tree[2 * i + 1]); }} - T comb(T a, T b) {return a + b;} // Modify this + E + T comb(T a, T b) { return a + b; } // Modify this + E void apply(int i, U val) { // And this + UF tree[i] = val * k[i]; @@ -42,17 +43,17 @@ struct SegTree { void update(int l, int r, U val) { l += n, r += n; int l0 = l, r0 = r; - push(l0), push(r0 - 1); + push(l0), push(r0); for (; l < r; l /= 2, r /= 2) { if (l&1) apply(l++, val); if (r&1) apply(--r, val); } - build(l0), build(r0 - 1); + build(l0), build(r0); } T query(int l, int r) { l += n, r += n; - push(l), push(r - 1); + push(l), push(r); T resL = E, resR = E; for (; l < r; l /= 2, r /= 2) { if (l&1) resL = comb(resL, tree[l++]); @@ -64,7 +65,7 @@ struct SegTree { // Optional: ll lower_bound(int l, int r, T x) { l += n, r += n; - push(l), push(r - 1); + push(l), push(r); vector<int> a, st; for (; l < r; l /= 2, r /= 2) { if (l&1) a.push_back(l++); diff --git a/datastructures/monotonicConvexHull.cpp b/datastructures/monotonicConvexHull.cpp index 44bff83..e7b9b3e 100644 --- a/datastructures/monotonicConvexHull.cpp +++ b/datastructures/monotonicConvexHull.cpp @@ -1,27 +1,26 @@ -// Lower Envelope mit MONOTONEN Inserts und Queries. Jede neue -// Gerade hat kleinere Steigung als alle vorherigen. -struct Line { - ll m, b; - ll operator()(ll x) {return m*x+b;} -}; +struct Envelope { + struct Line { + ll m, b; + ll operator()(ll x) { return m*x+b; } + }; -vector<Line> ls; -int ptr = 0; + vector<Line> ls; + int ptr = 0; -bool bad(Line l1, Line l2, Line l3) { - return (l3.b-l1.b)*(l1.m-l2.m) < (l2.b-l1.b)*(l1.m-l3.m); -} + static bool bad(Line l1, Line l2, Line l3) { + return (l3.b-l1.b)*(l1.m-l2.m) < (l2.b-l1.b)*(l1.m-l3.m); + } -void add(ll m, ll b) { // Laufzeit O(1) amortisiert - while (sz(ls) > 1 && bad(ls.end()[-2], ls.end()[-1], {m, b})) { - ls.pop_back(); + void add(ll m, ll b) { + while (sz(ls) > 1 && bad(ls.end()[-2], ls.back(), {m, b})) { + ls.pop_back(); + } + ls.push_back({m, b}); + ptr = min(ptr, sz(ls) - 1); } - ls.push_back({m, b}); - ptr = min(ptr, sz(ls) - 1); -} -ll query(ll x) { // Laufzeit: O(1) amortisiert - ptr = min(ptr, sz(ls) - 1); - while (ptr < sz(ls)-1 && ls[ptr + 1](x) < ls[ptr](x)) ptr++; - return ls[ptr](x); -}
\ No newline at end of file + ll query(ll x) { + while (ptr < sz(ls)-1 && ls[ptr + 1](x) < ls[ptr](x)) ptr++; + return ls[ptr](x); + } +}; diff --git a/datastructures/pbds.cpp b/datastructures/pbds.cpp index c2b44cc..a0e5383 100644 --- a/datastructures/pbds.cpp +++ b/datastructures/pbds.cpp @@ -1,10 +1,19 @@ +#include <ext/pb_ds/priority_queue.hpp> +template<typename T> +using pQueue = __gnu_pbds::priority_queue<T>; //<T, greater<T>> +auto it = pq.push(5); // O(1) +pq.modify(it, 6); // O(log n) +pq.erase(it); // O(log n) +pq.join(pq2); // O(1) +pq.swap(pq2); // O(1) + #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; -// T.order_of_key(x): number of elements strictly less than x -// *T.find_by_order(k): k-th element +T.order_of_key(x); // number of elements strictly less than x +auto it = T.find_by_order(k); // k-th element template<typename T> struct chash { diff --git a/datastructures/persistent.cpp b/datastructures/persistent.cpp index 0a65a79..4093cdc 100644 --- a/datastructures/persistent.cpp +++ b/datastructures/persistent.cpp @@ -7,7 +7,7 @@ struct persistent { : time(time), data(1, {time, value}) {}
T get(int t) {
- return prev(upper_bound(all(data), {t+1, {}}))->second;
+ return prev(upper_bound(all(data), pair{t+1, T{}}))->second;
}
int set(T value) {
diff --git a/datastructures/segmentTree.cpp b/datastructures/segmentTree.cpp index 79c6cae..4f75d03 100644 --- a/datastructures/segmentTree.cpp +++ b/datastructures/segmentTree.cpp @@ -4,14 +4,15 @@ struct SegTree { vector<T> tree; static constexpr T E = 0; // Neutral element for combine - SegTree(vector<T>& a) : n(sz(a)), tree(2 * n) { - //SegTree(int size, T val = E) : n(size), tree(2 * n, val) { - copy(all(a), tree.begin() + n); + SegTree(vector<T>& a) : n(ssize(a)), tree(2 * n, E) { + ranges::copy(a, tree.begin() + n); + //SegTree(int size, T val = E) : n(size), tree(2 * n, E) { + // fill(tree.begin() + n, tree.end(), val); for (int i = n - 1; i > 0; i--) { // remove for range update tree[i] = comb(tree[2 * i], tree[2 * i + 1]); }} - ll comb(T a, T b) {return a + b;} // modify this + neutral + ll comb(T a, T b) { return a + b; } // modify this + neutral void update(int i, T val) { tree[i += n] = val; // apply update code diff --git a/datastructures/sparseTable.cpp b/datastructures/sparseTable.cpp index 63cce48..64a892a 100644 --- a/datastructures/sparseTable.cpp +++ b/datastructures/sparseTable.cpp @@ -6,9 +6,9 @@ struct SparseTable { return a[lidx] <= a[ridx] ? lidx : ridx; } - void init(vector<ll> *vec) { - int n = sz(*vec); - a = vec->data(); + void init(vector<ll> &vec) { + int n = sz(vec); + a = vec.data(); st.assign(__lg(n) + 1, vector<int>(n)); iota(all(st[0]), 0); for (int j = 0; (2 << j) <= n; j++) { diff --git a/datastructures/sparseTableDisjoint.cpp b/datastructures/sparseTableDisjoint.cpp index 31e9025..dc5297a 100644 --- a/datastructures/sparseTableDisjoint.cpp +++ b/datastructures/sparseTableDisjoint.cpp @@ -1,5 +1,5 @@ struct DisjointST { - static constexpr ll neutral = 0 + static constexpr ll neutral = 0; vector<vector<ll>> dst; ll* a; @@ -7,16 +7,16 @@ struct DisjointST { return x + y; } - void init(vector<ll> *vec) { - int n = sz(*vec); - a = vec->data(); + void init(vector<ll> &vec) { + int n = sz(vec); + a = vec.data(); dst.assign(__lg(n) + 1, vector<ll>(n + 1, neutral)); for (int h = 0, l = 1; l <= n; h++, l *= 2) { for (int c = l; c < n + l; c += 2 * l) { for (int i = c; i < min(n, c + l); i++) - dst[h][i + 1] = combine(dst[h][i], vec->at(i)); + dst[h][i + 1] = combine(dst[h][i], vec[i]); for (int i = min(n, c); i > c - l; i--) - dst[h][i - 1] = combine(vec->at(i - 1), dst[h][i]); + dst[h][i - 1] = combine(vec[i - 1], dst[h][i]); }}} ll query(int l, int r) { diff --git a/datastructures/stlHashMap.cpp b/datastructures/stlHashMap.cpp deleted file mode 100644 index b107dde..0000000 --- a/datastructures/stlHashMap.cpp +++ /dev/null @@ -1,17 +0,0 @@ -#include <ext/pb_ds/assoc_container.hpp> -using namespace __gnu_pbds; - -template<typename T> -struct betterHash { - size_t operator()(T o) const { - size_t h = hash<T>()(o) ^ 42394245; //random value - h = ((h >> 16) ^ h) * 0x45d9f3b; - h = ((h >> 16) ^ h) * 0x45d9f3b; - h = ((h >> 16) ^ h); - return h; -}}; - -template<typename K, typename V, typename H = betterHash<K>> -using hashMap = gp_hash_table<K, V, H>; -template<typename K, typename H = betterHash<K>> -using hashSet = gp_hash_table<K, null_type, H>; diff --git a/datastructures/stlPQ.cpp b/datastructures/stlPQ.cpp deleted file mode 100644 index 4e439f8..0000000 --- a/datastructures/stlPQ.cpp +++ /dev/null @@ -1,15 +0,0 @@ -#include <ext/pb_ds/priority_queue.hpp> -template<typename T> -// greater<T> für Min-Queue -using priorityQueue = __gnu_pbds::priority_queue<T, less<T>>; - -int main() { - priorityQueue<int> pq; - auto it = pq.push(5); // O(1) - pq.push(7); - pq.pop(); // O(log n) amortisiert - pq.modify(it, 6); // O(log n) amortisiert - pq.erase(it); // O(log n) amortisiert - priorityQueue<int> pq2; - pq.join(pq2); // O(1) -} diff --git a/datastructures/stlPriorityQueue.cpp b/datastructures/stlPriorityQueue.cpp deleted file mode 100644 index 32b2455..0000000 --- a/datastructures/stlPriorityQueue.cpp +++ /dev/null @@ -1,8 +0,0 @@ -#include <ext/pb_ds/priority_queue.hpp> -template<typename T> -using pQueue = __gnu_pbds::priority_queue<T>; //<T, greater<T>> - -auto it = pq.push(5); -pq.modify(it, 6); -pq.join(pq2); -// push, join are O(1), pop, modify, erase O(log n) amortized diff --git a/datastructures/stlTree.cpp b/datastructures/stlTree.cpp deleted file mode 100644 index fbb68b9..0000000 --- a/datastructures/stlTree.cpp +++ /dev/null @@ -1,13 +0,0 @@ -#include <ext/pb_ds/assoc_container.hpp> -#include <ext/pb_ds/tree_policy.hpp> -using namespace std; using namespace __gnu_pbds; -template<typename T> -using Tree = tree<T, null_type, less<T>, rb_tree_tag, - tree_order_statistics_node_update>; - -int main() { - Tree<int> X; - for (int i : {1, 2, 4, 8, 16}) X.insert(i); - *X.find_by_order(3); // => 8 - X.order_of_key(10); // => 4 = min i, mit X[i] >= 10 -} diff --git a/datastructures/test/fenwickTree.cpp b/datastructures/test/fenwickTree.cpp new file mode 100644 index 0000000..f9dd619 --- /dev/null +++ b/datastructures/test/fenwickTree.cpp @@ -0,0 +1,26 @@ +#include "../fenwickTree.cpp" + +void test(int n) { + vector<ll> naive(n); + init(n); + + for (int i = 0; i < 1000; i++) { + int p = util::randint(n); + ll delta = util::randint(); + update(p, delta); + naive[p] += delta; + + int r = util::randint(n+1); + + ll naive_result = 0; + for (int i = 0; i < r; i++) naive_result += naive[i]; + ll fenwick_result = prefix_sum(r); + assert(naive_result == fenwick_result); + } +} + +int main() { + test(1); + test(100); + test(1000); +} diff --git a/datastructures/test/fenwickTree2.cpp b/datastructures/test/fenwickTree2.cpp new file mode 100644 index 0000000..18ebcb7 --- /dev/null +++ b/datastructures/test/fenwickTree2.cpp @@ -0,0 +1,28 @@ +#include "../fenwickTree2.cpp" + +void test(int n) { + vector<ll> naive(n); + for (int i = 0; i < n; i++) naive[i] = util::randint(); + init(naive); + + for (int i = 0; i < 1000; i++) { + int l = util::randint(n), r = util::randint(n); + if (l > r) swap(l, r); + ll delta = util::randint(); + update(l, r, delta); + for (int i = l; i < r; i++) naive[i] += delta; + + r = util::randint(n+1); + + ll naive_result = 0; + for (int i = 0; i < r; i++) naive_result += naive[i]; + ll fenwick_result = prefix_sum(r); + assert(naive_result == fenwick_result); + } +} + +int main() { + test(1); + test(100); + test(1000); +} diff --git a/datastructures/test/lazyPropagation.awk b/datastructures/test/lazyPropagation.awk new file mode 100644 index 0000000..fc39305 --- /dev/null +++ b/datastructures/test/lazyPropagation.awk @@ -0,0 +1,86 @@ + +/Neutral element for combine/ { + print "#ifndef SEGTREE_FIRST_NEG" + print "# ifndef SEGTREE_MAX" + print + print "# else" + tmp = $0 + sub(/0/, "numeric_limits<T>::min()", tmp) + print tmp + print "# endif" + print "#else" + sub(/0/, "numeric_limits<T>::max()") + print + print "#endif" + next +} + +/Modify this \+ E/ { + print "#ifndef SEGTREE_FIRST_NEG" + print "# ifndef SEGTREE_MAX" + print + print "# else" + tmp = $0 + sub(/a \+ b/, "max(a, b)", tmp) + print tmp + print "# endif" + print "#else" + sub(/a \+ b/, "a < 0 ? a : min(a, b)") + print + print "#endif" + next +} + +/Unused value by updates/ { + print "#ifndef SEGTREE_FIRST_NEG" + print + print "#else" + sub(/0/, /numeric_limits<U>::max()/) + print + print "#endif" + next +} + +/And this \+ UF/ { + print + getline set_tree + getline set_lazy + print "#ifndef SEGTREE_MAX" + print "# ifndef SEGTREE_FIRST_NEG" + print set_tree + print "# else" + tmp = set_tree + sub(/val \* k\[i\]/, "val", tmp) + print tmp + print "# endif" + print set_lazy + print "#else" + sub(/= val \* k\[i\]/, "+= val", set_tree) + sub(/= val/, "+= val", set_lazy) + print set_tree + print set_lazy + print "#endif" + next +} + +/Optional/ { print "#ifdef SEGTREE_MAX" } +/^\};$/ { print "#endif" } + +/SegTree\(const vector<T>& a\)/ { + print "#ifndef SEGTREE_INIT_DEFAULT" + print + print "#else" + getline + sub(/\/\//, "") + print + print "#endif" + getline + print + print "#ifndef SEGTREE_INIT_DEFAULT" + getline + print + print "#endif" + next +} + +{ print } diff --git a/datastructures/test/lazyPropagation.cpp b/datastructures/test/lazyPropagation.cpp new file mode 100644 index 0000000..df97b14 --- /dev/null +++ b/datastructures/test/lazyPropagation.cpp @@ -0,0 +1,102 @@ +#include "lazyPropagation.tmp.cpp" + +void test(int n) { +#ifndef SEGTREE_INIT_DEFAULT + vector<ll> a(n); + for (ll &x: a) x = util::randint(); + SegTree seg(a); +#else + ll init = util::randint(); +# ifdef SEGTREE_FIRST_NEG + init = abs(init); +# endif + vector<ll> a(n, init); + SegTree seg(n, init); +#endif + for (int i = 0; i < 5*n; i++) { + { + int l = util::randint(n+1); + int r = util::randint(n+1); + if (l > r) swap(l, r); + ll v = util::randint(); +#ifndef SEGTREE_FIRST_NEG +# ifndef SEGTREE_MAX + if (v == 0) v = 1; +# endif +#endif + for (int j = l; j < r; j++) { +#ifndef SEGTREE_MAX + a[j] = v; +#else + a[j] += v; +#endif + } + seg.update(l, r, v); + } + { + int l = util::randint(n+1); + int r = util::randint(n+1); + if (l > r) swap(l, r); +#ifndef SEGTREE_FIRST_NEG +# ifndef SEGTREE_MAX + ll comp = 0; +# else + ll comp = numeric_limits<ll>::min(); +# endif +#else + ll comp = numeric_limits<ll>::max(); +#endif + for (int j = l; j < r; j++) { +#ifndef SEGTREE_FIRST_NEG +# ifndef SEGTREE_MAX + comp += a[j]; +# else + comp = max(comp, a[j]); +# endif +#else + if (comp >= 0 && comp > a[j]) comp = a[j]; +#endif + } + assert(seg.query(l, r) == comp); + } +#ifdef SEGTREE_MAX + { + int l = util::randint(n+1); + int r = util::randint(n+1); + if (l > r) swap(l, r); + ll bound = util::randint(); + int found = -1; + for (int j = l; j < r; j++) { + if (a[j] >= bound) { + found = j; + break; + } + } + assert(seg.lower_bound(l, r, bound) == found); + } +#endif + } +} + +int main() { + test(1000); + test(1); + { +#ifndef SEGTREE_INIT_DEFAULT + vector<ll> a; + SegTree seg(a); +#else + SegTree seg(0); +#endif + seg.update(0, 0, util::randint()); +#ifndef SEGTREE_FIRST_NEG +# ifndef SEGTREE_MAX + assert(seg.query(0, 0) == 0); +# else + assert(seg.query(0, 0) == numeric_limits<ll>::min()); +# endif +#else + assert(seg.query(0, 0) == numeric_limits<ll>::max()); +#endif + } +} diff --git a/datastructures/test/monotonicConvexHull.cpp b/datastructures/test/monotonicConvexHull.cpp new file mode 100644 index 0000000..08927a2 --- /dev/null +++ b/datastructures/test/monotonicConvexHull.cpp @@ -0,0 +1,27 @@ +#define sz(X) ((int)size(X)) +#include "../monotonicConvexHull.cpp" + +int main() { + { + Envelope env; + env.add(10, 0); + assert(env.query(0) == 0); + assert(env.query(1) == 10); + env.add(8, 5); + assert(env.query(1) == 10); + assert(env.query(2) == 20); + assert(env.query(3) == 29); + env.add(7, 10); + assert(env.query(10) == 80); + env.add(0, 0); + assert(env.query(11) == 0); + } + + { + Envelope env; + env.add(1, 0); + env.add(0, 10); + env.add(-1, 10); + assert(env.query(7) == 3); + } +} diff --git a/datastructures/test/persistent.cpp b/datastructures/test/persistent.cpp new file mode 100644 index 0000000..5e5f864 --- /dev/null +++ b/datastructures/test/persistent.cpp @@ -0,0 +1,11 @@ +#define all(X) begin(X), end(X) +#include "../persistent.cpp" + +int main() { + int time = 0; + persistent<int> p(time, 0); + p.set(1); + int t1 = time; + p.set(2); + assert(p.get(t1) == 1); +} diff --git a/datastructures/test/segmentTree.awk b/datastructures/test/segmentTree.awk new file mode 100644 index 0000000..e863d4e --- /dev/null +++ b/datastructures/test/segmentTree.awk @@ -0,0 +1,74 @@ + +/Neutral element for combine/ { + print "#ifndef SEGTREE_MUL" + print "# ifndef SEGTREE_FIRST_NEG" + print + print "# else" + tmp = $0 + sub(/0/, "numeric_limits<ll>::max()", tmp) + print tmp + print "# endif" + print "#else" + sub(/0/, "1") + print + print "#endif" + next +} + +/modify this \+ neutral/ { + print "#ifndef SEGTREE_MUL" + print "# ifndef SEGTREE_FIRST_NEG" + print + print "# else" + tmp = $0 + sub(/a \+ b/, "a < 0 ? a : min(a, b)", tmp) + print tmp + print "# endif" + print "#else" + sub(/a \+ b/, "a*b % MOD") + print + print "#endif" + next +} + +/SegTree\(vector<T>& a\)/ { + print "#ifndef SEGTREE_INIT_DEFAULT" + print + getline + print + print "#else" + getline + sub(/\/\//, "") + print + getline + sub(/\/\//, "") + print + print "#endif" + next +} + +/remove for range update/ { + print "#ifndef SEGTREE_RANGE_UPDATE" + print + getline + print + getline + print "\t\t}" + print "#endif" + print "\t}" + next +} + +/void update/ { + print "#ifndef SEGTREE_RANGE_UPDATE" +} + +/OR: range update/ { + print "#else" +} + +/^\};$/ { + print "#endif" +} + +{ print } diff --git a/datastructures/test/segmentTree.cpp b/datastructures/test/segmentTree.cpp new file mode 100644 index 0000000..44d99b6 --- /dev/null +++ b/datastructures/test/segmentTree.cpp @@ -0,0 +1,100 @@ +#ifdef SEGTREE_MUL +constexpr ll MOD = 1'000'000'007; +#endif + +#include "segmentTree.tmp.cpp" + +void test(int n) { +#ifndef SEGTREE_INIT_DEFAULT + vector<ll> a(n); + for (ll &x: a) x = util::randint(); + SegTree seg(a); +#else + ll init = util::randint(); +# ifdef SEGTREE_FIRST_NEG + init = abs(init); +# endif + vector<ll> a(n, init); + SegTree seg(n, init); +#endif + for (int i = 0; i < 5*n; i++) { + { +#ifndef SEGTREE_RANGE_UPDATE + int j = util::randint(n); + ll v = util::randint(); + a[j] = v; + seg.update(j, v); +#else + int l = util::randint(n+1); + int r = util::randint(n+1); + if (l > r) swap(l, r); + ll v = util::randint(); + for (int j = l; j < r; j++) { +# ifndef SEGTREE_MUL + a[j] += v; +# else + a[j] = a[j]*v % MOD; +# endif + } + seg.modify(l, r, v); +#endif + } + { +#ifndef SEGTREE_RANGE_UPDATE + int l = util::randint(n+1); + int r = util::randint(n+1); + if (l > r) swap(l, r); +# ifndef SEGTREE_MUL +# ifndef SEGTREE_FIRST_NEG + ll comp = 0; +# else + ll comp = numeric_limits<ll>::max(); +# endif +# else + ll comp = 1; +# endif + for (int j = l; j < r; j++) { +# ifndef SEGTREE_MUL +# ifndef SEGTREE_FIRST_NEG + comp += a[j]; +# else + if (comp >= 0 && comp > a[j]) comp = a[j]; +# endif +# else + comp = comp * a[j] % MOD; +# endif + } + assert(seg.query(l, r) == comp); +#else + int j = util::randint(n); + assert(seg.query(j) == a[j]); +#endif + } + } +} + +int main() { + test(1000); + test(1); + { +#ifndef SEGTREE_INIT_DEFAULT + vector<ll> a; + SegTree seg(a); +#else + SegTree seg(0); +#endif +#ifndef SEGTREE_RANGE_UPDATE +# ifndef SEGTREE_MUL +# ifndef SEGTREE_FIRST_NEG + assert(seg.query(0, 0) == 0); +# else + assert(seg.query(0, 0) == numeric_limits<ll>::max()); +# endif +# else + assert(seg.query(0, 0) == 1); +# endif +#else + seg.modify(0, 0, util::randint()); +#endif + } +} diff --git a/datastructures/test/sparseTable.cpp b/datastructures/test/sparseTable.cpp new file mode 100644 index 0000000..03ef548 --- /dev/null +++ b/datastructures/test/sparseTable.cpp @@ -0,0 +1,26 @@ +#define sz ssize +#define all(X) begin(X), end(X) +#include "../sparseTable.cpp" + +void test(int n) { + vector<ll> values(n); + for (ll &x: values) x = util::randint(); + SparseTable st; + st.init(values); + for (int i = 0; i < n; i++) { + int l = util::randint(n); + int r = util::randint(n); + if (l > r) swap(l, r); + r++; + assert( + values[st.queryIdempotent(l, r)] + == + *min_element(values.begin()+l, values.begin()+r) + ); + } +} + +int main() { + test(1000); + test(1); +} diff --git a/datastructures/test/sparseTableDisjoint.cpp b/datastructures/test/sparseTableDisjoint.cpp new file mode 100644 index 0000000..7ef6483 --- /dev/null +++ b/datastructures/test/sparseTableDisjoint.cpp @@ -0,0 +1,26 @@ +#define sz ssize +#define all(X) begin(X), end(X) +#include "../sparseTableDisjoint.cpp" + +void test(int n) { + vector<ll> values(n); + for (ll &x: values) x = util::randint(); + DisjointST st; + st.init(values); + for (int i = 0; i < n; i++) { + int l = util::randint(n); + int r = util::randint(n); + if (l > r) swap(l, r); + r++; + assert( + st.query(l, r) + == + accumulate(values.begin()+l, values.begin()+r, 0ll) + ); + } +} + +int main() { + test(1000); + test(1); +} 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/unionFind2.cpp b/datastructures/unionFind2.cpp index 5362c4d..d1b9162 100644 --- a/datastructures/unionFind2.cpp +++ b/datastructures/unionFind2.cpp @@ -1,25 +1,26 @@ -vector<int> uf; +// unions[i] >= 0 => unions[i] = parent +// unions[i] < 0 => unions[i] = -size +vector<int> unions; -init(int N) { - uf.assign(N,-1); //-1 indicates that every subset has size 1 +init(int n) { + unions.assign(n, -1); } int findSet(int i) { - if(uf[i] < 0) return i; //If uf[i] < 0 we have reach a root - uf[i] = findSet(uf[i]); //Path-Compression - return uf[i]; + if (unions[i] < 0) return i; + return unions[i] = findSet(unions[i]); } -void linkSets(int i, int j) { - //Take |uf[i]|, where i must be a root, to get the size - //of the subset - if(abs(uf[i]) < abs(uf[j])) { //Union-by-size. - uf[j] += uf[i]; uf[i] = j; - } else { - uf[i] += uf[j]; uf[j] = i; - } +void linkSets(int a, int b) { // Union by size. + if (unions[b] > unions[a]) swap(a, b); + unions[b] += unions[a]; + unions[a] = b; } -void unionSets(int i, int j) { - if(findSet(i) != findSet(j)) linkSets(findSet(i),findSet(j)); +void unionSets(int a, int b) { + if (findSet(a) != findSet(b)) linkSets(findSet(a),findSet(b)); +} + +void getSize(int i) { + return -unions[findSet(i)]; } 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;} }; |