diff options
Diffstat (limited to 'content/datastructures')
23 files changed, 959 insertions, 0 deletions
diff --git a/content/datastructures/LCT.cpp b/content/datastructures/LCT.cpp new file mode 100644 index 0000000..c1dd278 --- /dev/null +++ b/content/datastructures/LCT.cpp @@ -0,0 +1,178 @@ +constexpr ll queryDefault = 0; +constexpr ll updateDefault = 0; + +ll _modify(ll x, ll y) { + return x + y; +} + +ll _query(ll x, ll y) { + return x + y; +} + +ll _update(ll delta, int length) { + if (delta == updateDefault) return updateDefault; + //ll result = delta + //for (int i=1; i<length; i++) result = _query(result, delta); + return delta * length; +} + +//generic: +ll joinValueDelta(ll value, ll delta) { + if (delta == updateDefault) return value; + return _modify(value, delta); +} + +ll joinDeltas(ll delta1, ll delta2) { + if (delta1 == updateDefault) return delta2; + if (delta2 == updateDefault) return delta1; + return _modify(delta1, delta2); +} + +struct LCT { + struct Node { + ll nodeValue, subTreeValue, delta; + bool revert; + int id, size; + Node *left, *right, *parent; + + Node(int id = 0, int val = queryDefault) : + nodeValue(val), subTreeValue(val), delta(updateDefault), + revert(false), id(id), size(1), + left(nullptr), right(nullptr), parent(nullptr) {} + + bool isRoot() { + return !parent || (parent->left != this && + parent->right != this); + } + + void push() { + if (revert) { + revert = false; + swap(left, right); + if (left) left->revert ^= 1; + if (right) right->revert ^= 1; + } + nodeValue = joinValueDelta(nodeValue, delta); + subTreeValue = joinValueDelta(subTreeValue, + _update(delta, size)); + if (left) left->delta = joinDeltas(left->delta, delta); + if (right) right->delta = joinDeltas(right->delta, delta); + delta = updateDefault; + } + + ll getSubtreeValue() { + return joinValueDelta(subTreeValue, _update(delta, size)); + } + + void update() { + subTreeValue = joinValueDelta(nodeValue, delta); + size = 1; + if (left) { + subTreeValue = _query(subTreeValue, + left->getSubtreeValue()); + size += left->size; + } + if (right) { + subTreeValue = _query(subTreeValue, + right->getSubtreeValue()); + size += right->size; + }} + }; + + vector<Node> nodes; + + LCT(int n) : nodes(n) { + for (int i = 0; i < n; i++) nodes[i].id = i; + } + + void connect(Node* ch, Node* p, int isLeftChild) { + if (ch) ch->parent = p; + if (isLeftChild >= 0) { + if (isLeftChild) p->left = ch; + else p->right = ch; + }} + + void rotate(Node* x) { + Node* p = x->parent; + Node* g = p->parent; + bool isRootP = p->isRoot(); + bool leftChildX = (x == p->left); + + connect(leftChildX ? x->right : x->left, p, leftChildX); + connect(p, x, !leftChildX); + connect(x, g, isRootP ? -1 : p == g->left); + p->update(); + } + + void splay(Node* x) { + while (!x->isRoot()) { + Node* p = x->parent; + Node* g = p->parent; + if (!p->isRoot()) g->push(); + p->push(); + x->push(); + if (!p->isRoot()) rotate((x == p->left) == + (p == g->left) ? p : x); + rotate(x); + } + x->push(); + x->update(); + } + + Node* expose(Node* x) { + Node* last = nullptr; + for (Node* y = x; y; y = y->parent) { + splay(y); + y->left = last; + last = y; + } + splay(x); + return last; + } + + void makeRoot(Node* x) { + expose(x); + x->revert ^= 1; + } + + bool connected(Node* x, Node* y) { + if (x == y) return true; + expose(x); + expose(y); + return x->parent; + } + + void link(Node* x, Node* y) { + assert(!connected(x, y)); // not yet connected! + makeRoot(x); + x->parent = y; + } + + void cut(Node* x, Node* y) { + makeRoot(x); + expose(y); + //must be a tree edge! + assert(!(y->right != x || x->left != nullptr)); + y->right->parent = nullptr; + y->right = nullptr; + } + + Node* lca(Node* x, Node* y) { + assert(connected(x, y)); + expose(x); + return expose(y); + } + + ll query(Node* from, Node* to) { + makeRoot(from); + expose(to); + if (to) return to->getSubtreeValue(); + return queryDefault; + } + + void modify(Node* from, Node* to, ll delta) { + makeRoot(from); + expose(to); + to->delta = joinDeltas(to->delta, delta); + } +}; diff --git a/content/datastructures/bitset.cpp b/content/datastructures/bitset.cpp new file mode 100644 index 0000000..d19abb0 --- /dev/null +++ b/content/datastructures/bitset.cpp @@ -0,0 +1,7 @@ +bitset<10> bits(0b000010100); +bits._Find_first(); //2 +bits._Find_next(2); //4 +bits._Find_next(4); //10 bzw. N +bits[x] = 1; //not bits.set(x) or bits.reset(x)! +bits[x].flip(); //not bits.flip(x)! +bits.count(); //number of set bits diff --git a/content/datastructures/datastructures.tex b/content/datastructures/datastructures.tex new file mode 100644 index 0000000..40132a9 --- /dev/null +++ b/content/datastructures/datastructures.tex @@ -0,0 +1,121 @@ +\section{Datenstrukturen} + +\begin{algorithm}{Segmentbaum} + \begin{methods} + \method{SegTree}{baut den Baum auf}{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)} + \sourcecode{datastructures/lazyPropagation.cpp} +\end{algorithm} + +\begin{algorithm}{Wavelet Tree} + \begin{methods} + \method{WaveletTree}{baut den Baum auf}{n\*\log(\Sigma)} + \method{kth}{sort $[l, r)[k]$}{\log(\Sigma)} + \method{countSmaller}{Anzahl elemente in $[l, r)$ kleiner als $k$}{\log(\Sigma)} + \end{methods} + \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{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)$. $l\leq r$!}{\log(n)} + \end{methods} + \sourcecode{datastructures/fenwickTree2.cpp} +\end{algorithm} + +\begin{algorithm}{STL-Rope (Implicit Cartesian Tree)} + \sourcecode{datastructures/stlRope.cpp} +\end{algorithm} +\columnbreak + +\begin{algorithm}{(Implicit) Treap (Cartesian Tree)} + \begin{methods} + \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} +\end{algorithm} + +\begin{algorithm}{Range Minimum Query} + \begin{methods} + \method{init}{baut Struktur auf}{n\*\log(n)} + \method{queryIdempotent}{Index des Minimums in $[l, r)$. $l<r$!}{1} + \end{methods} + \begin{itemize} + \item \code{better}-Funktion muss idempotent sein! + \end{itemize} + \sourcecode{datastructures/sparseTable.cpp} +\end{algorithm} + +\begin{algorithm}{STL-Bitset} + \sourcecode{datastructures/bitset.cpp} +\end{algorithm} + +\begin{algorithm}{Link-Cut-Tree} + \begin{methods} + \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)} + \method{lca}{berechnet LCA von $x$ und $y$}{\log(n)} + \method{query}{berechnet \code{query} auf den Knoten des $xy$-Pfades}{\log(n)} + \method{modify}{erhöht jeden wert auf dem $xy$-Pfad}{\log(n)} + \end{methods} + \sourcecode{datastructures/LCT.cpp} +\end{algorithm} +\clearpage + +\begin{algorithm}{Lichao} + \sourcecode{datastructures/lichao.cpp} +\end{algorithm} + +\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. + \sourcecode{datastructures/monotonicConvexHull.cpp} + \sourcecode{datastructures/dynamicConvexHull.cpp} +\end{algorithm} + +\begin{algorithm}{Union-Find} + \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{m\*findSet + n\*unionSets}{Folge von Befehlen}{n+m\*\alpha(n)} + \end{methods} + \sourcecode{datastructures/unionFind.cpp} +\end{algorithm} +\columnbreak + +\begin{algorithm}{Persistent} + \begin{methods} + \method{get}{berechnet Wert zu Zeitpunkt $t$}{\log(t)} + \method{set}{ändert Wert zu Zeitpunkt $t$}{\log(t)} + \method{reset}{setzt die Datenstruktur auf Zeitpunkt $t$}{1} + \end{methods} + \sourcecode{datastructures/persistent.cpp} + \sourcecode{datastructures/persistentArray.cpp} +\end{algorithm} diff --git a/content/datastructures/dynamicConvexHull.cpp b/content/datastructures/dynamicConvexHull.cpp new file mode 100644 index 0000000..d669847 --- /dev/null +++ b/content/datastructures/dynamicConvexHull.cpp @@ -0,0 +1,36 @@ +struct Line { + mutable ll m, b, p; + bool operator<(const Line& o) const {return m < o.m;} + bool operator<(ll x) const {return p < x;} +}; + +struct HullDynamic : multiset<Line, less<>> { + // (for doubles, use inf = 1/.0, div(a,b) = a/b) + ll div(ll a, ll b) {return a / b - ((a ^ b) < 0 && a % b);} + + bool isect(iterator x, iterator y) { + if (y == end()) {x->p = INF; return false;} + if (x->m == y->m) x->p = x->b > y->b ? INF : -INF; + else x->p = div(y->b - x->b, x->m - y->m); + return x->p >= y->p; + } + + void add(ll m, ll b) { + 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)); + }} + while (x != begin() && prev(x)->p >= x->p) { + x--; + isect(x, erase(next(x))); + }} + + ll query(ll x) { + auto l = *lower_bound(x); + return l.m * x + l.b; + } +}; diff --git a/content/datastructures/fenwickTree.cpp b/content/datastructures/fenwickTree.cpp new file mode 100644 index 0000000..eb5cd73 --- /dev/null +++ b/content/datastructures/fenwickTree.cpp @@ -0,0 +1,15 @@ +vector<ll> tree; + +void update(int i, ll val) { + for (i++; i < sz(tree); i += i & -i) tree[i] += val; +} + +void init(int n) { + tree.assign(n + 1, 0); +} + +ll prefix_sum(int i) { + ll sum = 0; + for (i++; i > 0; i -= i & -i) sum += tree[i]; + return sum; +} diff --git a/content/datastructures/fenwickTree2.cpp b/content/datastructures/fenwickTree2.cpp new file mode 100644 index 0000000..9384e3c --- /dev/null +++ b/content/datastructures/fenwickTree2.cpp @@ -0,0 +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) + add[tl] += val, mul[tl] -= val * l; + for (int tr = r + 1; tr < sz(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]); +} + +ll prefix_sum(int i) { + ll res = 0; i++; + for (int ti = i; ti > 0; ti -= ti & -ti) + res += add[ti] * i + mul[ti]; + return res; +} diff --git a/content/datastructures/lazyPropagation.cpp b/content/datastructures/lazyPropagation.cpp new file mode 100644 index 0000000..441590e --- /dev/null +++ b/content/datastructures/lazyPropagation.cpp @@ -0,0 +1,85 @@ +struct SegTree { + using T = ll; using U = ll; + int n; + static constexpr T E = 0; // Neutral element for combine + static constexpr U UF = inf; // Unused value by updates + vector<T> tree; + int h; + vector<U> lazy; + vector<int> k; // size of segments (optional) + + SegTree(const vector<T>& a) : n(sz(a) + 1), tree(2 * n, E), + //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); + 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 + + void apply(int i, U val) { // And this + UF + tree[i] = val * k[i]; + if (i < n) lazy[i] = val; // Don't forget this + } + + void push_down(int i) { + if (lazy[i] != UF) { + apply(2 * i, lazy[i]); + apply(2 * i + 1, lazy[i]); + lazy[i] = UF; + }} + + void push(int i) { + for (int s = h; s > 0; s--) push_down(i >> s); + } + + void build(int i) { + while (i /= 2) { + push_down(i); + tree[i] = comb(tree[2 * i], tree[2 * i + 1]); + }} + + void update(int l, int r, U val) { + l += n, r += n; + int l0 = l, r0 = r; + push(l0), push(r0 - 1); + for (; l < r; l /= 2, r /= 2) { + if (l&1) apply(l++, val); + if (r&1) apply(--r, val); + } + build(l0), build(r0 - 1); + } + + T query(int l, int r) { + l += n, r += n; + push(l), push(r - 1); + T resL = E, resR = E; + for (; l < r; l /= 2, r /= 2) { + if (l&1) resL = comb(resL, tree[l++]); + if (r&1) resR = comb(tree[--r], resR); + } + return comb(resL, resR); + } + + // Optional: + int lower_bound(int l, int r, T x) { + l += n, r += n; + push(l), push(r - 1); + int a[64] = {}, lp = 0, rp = 64; + for (; l < r; l /= 2, r /= 2) { + if (l&1) a[lp++] = l++; + if (r&1) a[--rp] = --r; + } + for (int i : a) if (i != 0 && tree[i] >= x) { // Modify this + while (i < n) { + push_down(i); + if (tree[2 * i] >= x) i = 2 * i; // And this + else i = 2 * i + 1; + } + return i - n; + } + return -1; + } +}; diff --git a/content/datastructures/lichao.cpp b/content/datastructures/lichao.cpp new file mode 100644 index 0000000..f66778e --- /dev/null +++ b/content/datastructures/lichao.cpp @@ -0,0 +1,46 @@ +vector<ll> xs; // IMPORTANT: Initialize before constructing! +int findX(int i) {return lower_bound(all(xs), i) - begin(xs);} + +struct Fun { // Default: Linear function. Change as needed. + ll m, c; + ll operator()(int x) {return m*xs[x] + c;} +}; + +// Default: Computes min. Change lines with comment for max. +struct Lichao { + static constexpr Fun id = {0, inf}; // {0, -inf} + int n, cap; + vector<Fun> seg; + Lichao() : n(sz(xs)), cap(2<<__lg(n)), seg(2*cap, id) {} + + void _insert(Fun f, int l, int r, int i) { + while (i < 2*cap){ + int m = (l+r)/2; + if (m >= n) {r = m; i = 2*i; continue;} + Fun &g = seg[i]; + if (f(m) < g(m)) swap(f, g); // > + if (f(l) < g(l)) r = m, i = 2*i; // > + else l = m, i = 2*i+1; + }} + void insert(Fun f) {_insert(f, 0, cap, 1);} + + void _segmentInsert(Fun f, int l, int r, int a, int b, int i) { + if (l <= a && b <= r) _insert(f, a, b, i); + else if (a < r && l < b){ + int m = (a+b)/2; + _segmentInsert(f, l, r, a, m, 2*i); + _segmentInsert(f, l, r, m, b, 2*i+1); + }} + void segmentInsert(Fun f, ll l, ll r) { + _segmentInsert(f, findX(l), findX(r), 0, cap, 1); + } + + ll _query(int x) { + ll ans = inf; // -inf + for (int i = x + cap; i > 0; i /= 2) { + ans = min(ans, seg[i](x)); // max + } + return ans; + } + ll query(ll x) {return _query(findX(x));} +}; diff --git a/content/datastructures/monotonicConvexHull.cpp b/content/datastructures/monotonicConvexHull.cpp new file mode 100644 index 0000000..44bff83 --- /dev/null +++ b/content/datastructures/monotonicConvexHull.cpp @@ -0,0 +1,27 @@ +// 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;} +}; + +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); +} + +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(); + } + 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 diff --git a/content/datastructures/pbds.cpp b/content/datastructures/pbds.cpp new file mode 100644 index 0000000..f0889a2 --- /dev/null +++ b/content/datastructures/pbds.cpp @@ -0,0 +1,18 @@ +#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 + +template<typename T> +struct chash { + static const uint64_t C = ll(2e18 * acos(-1)) | 199; // random odd + size_t operator()(T o) const { + return __builtin_bswap64(hash<T>()(o) * C); +}}; +template<typename K, typename V> +using hashMap = gp_hash_table<K, V, chash<K>>; +template<typename T> +using hashSet = gp_hash_table<T, null_type, chash<T>>; diff --git a/content/datastructures/persistent.cpp b/content/datastructures/persistent.cpp new file mode 100644 index 0000000..4093cdc --- /dev/null +++ b/content/datastructures/persistent.cpp @@ -0,0 +1,18 @@ +template<typename T>
+struct persistent {
+ int& time;
+ vector<pair<int, T>> data;
+
+ persistent(int& time, T value = {})
+ : time(time), data(1, {time, value}) {}
+
+ T get(int t) {
+ return prev(upper_bound(all(data), pair{t+1, T{}}))->second;
+ }
+
+ int set(T value) {
+ time += 2;
+ data.push_back({time, value});
+ return time;
+ }
+};
diff --git a/content/datastructures/persistentArray.cpp b/content/datastructures/persistentArray.cpp new file mode 100644 index 0000000..60d8b17 --- /dev/null +++ b/content/datastructures/persistentArray.cpp @@ -0,0 +1,24 @@ +template<typename T>
+struct persistentArray {
+ int time;
+ vector<persistent<T>> data;
+ vector<pair<int, int>> mods;
+
+ persistentArray(int n, T value = {})
+ : time(0), data(n, {time, value}) {}
+
+ T get(int p, int t) {return data[p].get(t);}
+
+ int set(int p, T value) {
+ mods.push_back({p, time});
+ return data[p].set(value);
+ }
+
+ void reset(int t) {
+ while (!mods.empty() && mods.back().second > t) {
+ data[mods.back().first].data.pop_back();
+ mods.pop_back();
+ }
+ time = t;
+ }
+};
diff --git a/content/datastructures/segmentTree.cpp b/content/datastructures/segmentTree.cpp new file mode 100644 index 0000000..6b69d0b --- /dev/null +++ b/content/datastructures/segmentTree.cpp @@ -0,0 +1,42 @@ +struct SegTree { + using T = ll; + int n; + 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); + for (int i = n - 1; i > 0; i--) { // remove for range update + tree[i] = comb(tree[2 * i], tree[2 * i + 1]); + }} + + T comb(T a, T b) {return a + b;} // modify this + neutral + + void update(int i, T val) { + tree[i += n] = val; // apply update code + while (i /= 2) tree[i] = comb(tree[2 * i], tree[2 * i + 1]); + } + + T query(int l, int r) { + T resL = E, resR = E; + for (l += n, r += n; l < r; l /= 2, r /= 2) { + if (l&1) resL = comb(resL, tree[l++]); + if (r&1) resR = comb(tree[--r], resR); + } + return comb(resL, resR); + } + + // OR: range update + point query, needs commutative comb + void modify(int l, int r, T val) { + for (l += n, r += n; l < r; l /= 2, r /= 2) { + if (l&1) tree[l] = comb(tree[l], val), l++; + if (r&1) --r, tree[r] = comb(tree[r], val); + }} + + T query(int i) { + T res = E; + for (i += n; i > 0; i /= 2) res = comb(res, tree[i]); + return res; + } +}; diff --git a/content/datastructures/sparseTable.cpp b/content/datastructures/sparseTable.cpp new file mode 100644 index 0000000..b3f946e --- /dev/null +++ b/content/datastructures/sparseTable.cpp @@ -0,0 +1,24 @@ +struct SparseTable { + vector<vector<int>> st; + ll *a; + + int better(int lidx, int ridx) { + return a[lidx] <= a[ridx] ? lidx : ridx; + } + + 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++) { + for (int i = 0; i + (2 << j) <= n; i++) { + st[j + 1][i] = better(st[j][i] , st[j][i + (1 << j)]); + }}} + + int queryIdempotent(int l, int r) { + if (r <= l) return -1; + int j = __lg(r - l); //31 - builtin_clz(r - l); + return better(st[j][l] , st[j][r - (1 << j)]); + } +}; diff --git a/content/datastructures/sparseTableDisjoint.cpp b/content/datastructures/sparseTableDisjoint.cpp new file mode 100644 index 0000000..55165d4 --- /dev/null +++ b/content/datastructures/sparseTableDisjoint.cpp @@ -0,0 +1,27 @@ +struct DisjointST { + static constexpr ll neutral = 0; + vector<vector<ll>> dst; + ll* a; + + ll combine(const ll& x, const ll& y) { + return x + y; + } + + 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)); + for (int i = min(n, c); i > c - l; i--) + dst[h][i - 1] = combine(vec->at(i - 1), dst[h][i]); + }}} + + ll query(int l, int r) { + if (r <= l) return neutral; + int h = __lg(l ^ r); + return combine(dst[h][l], dst[h][r]); + } +}; diff --git a/content/datastructures/stlHashMap.cpp b/content/datastructures/stlHashMap.cpp new file mode 100644 index 0000000..b107dde --- /dev/null +++ b/content/datastructures/stlHashMap.cpp @@ -0,0 +1,17 @@ +#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/content/datastructures/stlPriorityQueue.cpp b/content/datastructures/stlPriorityQueue.cpp new file mode 100644 index 0000000..32b2455 --- /dev/null +++ b/content/datastructures/stlPriorityQueue.cpp @@ -0,0 +1,8 @@ +#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/content/datastructures/stlRope.cpp b/content/datastructures/stlRope.cpp new file mode 100644 index 0000000..804cd67 --- /dev/null +++ b/content/datastructures/stlRope.cpp @@ -0,0 +1,8 @@ +#include <ext/rope> +using namespace __gnu_cxx; +rope<int> v; // Wie normaler Container. +v.push_back(num); // O(log(n)) +rope<int> sub = v.substr(start, length); // O(log(n)) +v.erase(start, length); // O(log(n)) +v.insert(v.mutable_begin() + offset, sub); // O(log(n)) +for(auto it = v.mutable_begin(); it != v.mutable_end(); it++) diff --git a/content/datastructures/stlTree.cpp b/content/datastructures/stlTree.cpp new file mode 100644 index 0000000..fbb68b9 --- /dev/null +++ b/content/datastructures/stlTree.cpp @@ -0,0 +1,13 @@ +#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/content/datastructures/treap.cpp b/content/datastructures/treap.cpp new file mode 100644 index 0000000..c96e36a --- /dev/null +++ b/content/datastructures/treap.cpp @@ -0,0 +1,79 @@ +struct node { + int key, prio, left, right, size; + node(int key, int prio) : key(key), prio(prio), left(-1), + right(-1), size(1) {}; +}; + +vector<node> treap; + +int getSize(int root) { + return root < 0 ? 0 : treap[root].size; +} + +void update(int root) { + if (root < 0) return; + treap[root].size = 1 + getSize(treap[root].left) + + getSize(treap[root].right); +} + +pair<int, int> split(int root, int minKeyRight) { + if (root < 0) return {-1, -1}; + if (treap[root].key >= minKeyRight) { + auto leftSplit = split(treap[root].left, minKeyRight); + treap[root].left = leftSplit.second; + update(root); + leftSplit.second = root; + return leftSplit; + } else { + auto rightSplit = split(treap[root].right, minKeyRight); + treap[root].right = rightSplit.first; + update(root); + rightSplit.first = root; + return rightSplit; +}} + +int merge (int left, int right) { + if (left < 0) return right; + if (right < 0) return left; + if (treap[left].prio < treap[right].prio) { //min priority heap + treap[left].right = merge(treap[left].right, right); + update(left); + return left; + } else { + treap[right].left = merge(left, treap[right].left); + update(right); + return right; +}} + +//insert values with high priority first +int insert(int root, int key, int prio) { + int next = sz(treap); + treap.emplace_back(key, prio); + auto t = split(root, key); + //returns new root + return merge(merge(t.first, next), t.second); +} + +int remove(int root, int key) { + if (root < 0) return -1; + if (key < treap[root].key) { + treap[root].left = remove(treap[root].left, key); + update(root); + return root; + } else if (key > treap[root].key) { + treap[root].right = remove(treap[root].right, key); + update(root); + return root; + } else { //check prio? + return merge(treap[root].left, treap[root].right); +}} + +int kth(int root, int k) { + if (root < 0) return -1; + int leftSize = getSize(treap[root].left); + if (k < leftSize) return kth(treap[root].left, k); + else if (k > leftSize) { + return kth(treap[root].right, k - 1 - leftSize); + } + return root; +} diff --git a/content/datastructures/treap2.cpp b/content/datastructures/treap2.cpp new file mode 100644 index 0000000..c5a60e9 --- /dev/null +++ b/content/datastructures/treap2.cpp @@ -0,0 +1,79 @@ +mt19937 rng(0xc4bd5dad); +struct Treap { + struct Node { + ll val; + int prio, size = 1, l = -1, r = -1; + Node(ll x) : val(x), prio(rng()) {} + }; + + vector<Node> treap; + int root = -1; + + int getSize(int v) { + return v < 0 ? 0 : treap[v].size; + } + + void upd(int v) { + if (v < 0) return; + auto& V = treap[v]; + V.size = 1 + getSize(V.l) + getSize(V.r); + // Update Node Code + } + + void push(int v) { + if (v < 0) return; + //auto& V = treap[v]; + //if (V.lazy) { + // Lazy Propagation Code + // if (V.l >= 0) treap[V.l].lazy = true; + // if (V.r >= 0) treap[V.r].lazy = true; + // V.lazy = false; + //} + } + + pair<int, int> split(int v, int k) { + if (v < 0) return {-1, -1}; + auto& V = treap[v]; + push(v); + if (getSize(V.l) >= k) { // "V.val >= k" for lower_bound(k) + auto [left, right] = split(V.l, k); + V.l = right; + upd(v); + return {left, v}; + } else { + // and only "k" + auto [left, right] = split(V.r, k - getSize(V.l) - 1); + V.r = left; + upd(v); + return {v, right}; + }} + + int merge(int left, int right) { + if (left < 0) return right; + if (right < 0) return left; + if (treap[left].prio < treap[right].prio) { + push(left); + treap[left].r = merge(treap[left].r, right); + upd(left); + return left; + } else { + push(right); + treap[right].l = merge(left, treap[right].l); + upd(right); + return right; + }} + + void insert(int i, ll val) { // and i = val + auto [left, right] = split(root, i); + treap.emplace_back(val); + left = merge(left, sz(treap) - 1); + root = merge(left, right); + } + + void remove(int i, int count = 1) { + auto [left, t_right] = split(root, i); + auto [middle, right] = split(t_right, count); + root = merge(left, right); + } + // for query use remove and read middle BEFORE remerging +}; diff --git a/content/datastructures/unionFind.cpp b/content/datastructures/unionFind.cpp new file mode 100644 index 0000000..dd5a569 --- /dev/null +++ b/content/datastructures/unionFind.cpp @@ -0,0 +1,26 @@ +// unions[i] >= 0 => unions[i] = parent +// unions[i] < 0 => unions[i] = -size +vector<int> unions; + +void init(int n) { //Initialisieren + unions.assign(n, -1); +} + +int findSet(int a) { // Pfadkompression + if (unions[a] < 0) return a; + return unions[a] = findSet(unions[a]); +} + +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 a, int b) { // Diese Funktion aufrufen. + if (findSet(a) != findSet(b)) linkSets(findSet(a), findSet(b)); +} + +int size(int a) { + return -unions[findSet(a)]; +} diff --git a/content/datastructures/waveletTree.cpp b/content/datastructures/waveletTree.cpp new file mode 100644 index 0000000..090cdb2 --- /dev/null +++ b/content/datastructures/waveletTree.cpp @@ -0,0 +1,40 @@ +struct WaveletTree { + using it = vector<ll>::iterator; + WaveletTree *ln = nullptr, *rn = nullptr; + 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) { + 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)); + } + if (lo + 1 >= hi) return; + it pivot = stable_partition(from, to, f); + ln = new WaveletTree(from, pivot); + rn = new WaveletTree(pivot, to); + } + + // kth element in sort[l, r) all 0-indexed + ll kth(int l, int r, int k) { + if (k < 0 || l + k >= r) return -1; + if (lo + 1 >= hi) return lo; + int inLeft = b[r] - b[l]; + if (k < inLeft) return ln->kth(b[l], b[r], k); + 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;} +}; |