diff options
Diffstat (limited to 'datastructures')
| -rw-r--r-- | datastructures/datastructures.tex | 15 | ||||
| -rw-r--r-- | datastructures/fenwickTreeNiklas.cpp | 56 | ||||
| -rw-r--r-- | datastructures/firstUnused.cpp | 12 | ||||
| -rw-r--r-- | datastructures/segmentTree.cpp | 2 | ||||
| -rw-r--r-- | datastructures/segmentTree2D.cpp | 58 | ||||
| -rw-r--r-- | datastructures/skewHeap.cpp | 29 | ||||
| -rw-r--r-- | datastructures/sparseTable.cpp | 27 | ||||
| -rw-r--r-- | datastructures/unionFind2.cpp | 27 |
8 files changed, 178 insertions, 48 deletions
diff --git a/datastructures/datastructures.tex b/datastructures/datastructures.tex index a2c5ff6..b3683bf 100644 --- a/datastructures/datastructures.tex +++ b/datastructures/datastructures.tex @@ -5,15 +5,16 @@ \subsection{Segmentbaum} \lstinputlisting{datastructures/segmentTree.cpp} -Mit \lstinline{update()} können ganze Intervalle geändert werden. -Dazu: Offset in den inneren Knoten des Baums speichern. + +\subsection{2D-Segmentbaum} +\lstinputlisting{datastructures/segmentTree2D.cpp} \subsection{Fenwick Tree} \lstinputlisting{datastructures/fenwickTree.cpp} +\lstinputlisting{datastructures/fenwickTreeNiklas.cpp} - -\subsection{Range Minimum Query} -\lstinputlisting{datastructures/RMQ.cpp} +\subsection{Sparse Table} +\lstinputlisting{datastructures/sparseTable.cpp} \subsection{STL-Tree} \lstinputlisting{datastructures/stlTree.cpp} @@ -24,5 +25,5 @@ Dazu: Offset in den inneren Knoten des Baums speichern. \subsection{Treap (Cartesian Tree)} \lstinputlisting{datastructures/treap.cpp} -\subsection{Erste unbenutzte natürliche Zahl} -\lstinputlisting{datastructures/firstUnused.cpp} +\subsection{Skew Heap} +\lstinputlisting{datastructures/skewHeap.cpp} diff --git a/datastructures/fenwickTreeNiklas.cpp b/datastructures/fenwickTreeNiklas.cpp new file mode 100644 index 0000000..032f74c --- /dev/null +++ b/datastructures/fenwickTreeNiklas.cpp @@ -0,0 +1,56 @@ +const int n = 10000; // ALL INDICES START AT 1 WITH THIS CODE!! + +// mode 1: update indices, read prefixes +void update_idx(int tree[], int i, int val) { // v[i] += val + for (; i <= n; i += i & -i) tree[i] += val; +} +int read_prefix(int tree[], int i) { // get sum v[1..i] + int sum = 0; + for (; i > 0; i -= i & -i) sum += tree[i]; + return sum; +} +int kth(int k) { // find kth element in tree (1-based index) + int ans = 0; + for (int i = maxl; i >= 0; --i) // maxl = largest i s.t. (1<<i) <= n + if (ans + (1<<i) <= n && tree[ans + (1<<i)] < k) { + ans += 1<<i; + k -= tree[ans]; + } + return ans+1; +} + +// mode 2: update prefixes, read indices +void update_prefix(int tree[], int i, int val) { // v[1..i] += val + for (; i > 0; i -= i & -i) tree[i] += val; +} +int read_idx(int tree[], int i) { // get v[i] + int sum = 0; + for (; i <= n; i += i & -i) sum += tree[i]; + return sum; +} + +// mode 3: range-update range-query +const int maxn = 100100; +int n; +ll mul[maxn], add[maxn]; + +void update_idx(ll tree[], int x, ll val) { + for (int i = x; i <= n; i += i & -i) tree[i] += val; +} +void update_prefix(int x, ll val) { // v[x] += val + update_idx(mul, 1, val); + update_idx(mul, x + 1, -val); + update_idx(add, x + 1, x * val); +} +ll read_prefix(int x) { // get sum v[1..x] + ll a = 0, b = 0; + for (int i = x; i > 0; i -= i & -i) a += mul[i], b += add[i]; + return a * x + b; +} +void update_range(int l, int r, ll val) { // v[l..r] += val + update_prefix(l - 1, -val); + update_prefix(r, val); +} +ll read_range(int l, int r) { // get sum v[l..r] + return read_prefix(r) - read_prefix(l - 1); +} diff --git a/datastructures/firstUnused.cpp b/datastructures/firstUnused.cpp deleted file mode 100644 index 141eb00..0000000 --- a/datastructures/firstUnused.cpp +++ /dev/null @@ -1,12 +0,0 @@ -// Erste natürliche Zahl nicht im set used. -set<int> used; -int unusedCounter = 1; - -int getFirstUnused() { // Laufzeit: O(log n) amortisiert. - auto it = used.lower_bound(unusedCounter); - while (it != used.end() && *it == unusedCounter) { - it++; - unusedCounter++; - } - return unusedCounter++; // Evtl. neuen Wert noch hinzufügen. -} diff --git a/datastructures/segmentTree.cpp b/datastructures/segmentTree.cpp index c810af7..3905151 100644 --- a/datastructures/segmentTree.cpp +++ b/datastructures/segmentTree.cpp @@ -2,8 +2,6 @@ // Berechnet das Maximum im Array. int a[MAX_N], m[4 * MAX_N]; -int gcd(int a, int b) { return b == 0 ? a : gcd (b, a % b); } - int query(int x, int y, int k = 0, int X = 0, int Y = MAX_N - 1) { if (x <= X && Y <= y) return m[k]; if (y < X || Y < x) return -INF; // Ein "neutrales" Element. diff --git a/datastructures/segmentTree2D.cpp b/datastructures/segmentTree2D.cpp new file mode 100644 index 0000000..a9d129b --- /dev/null +++ b/datastructures/segmentTree2D.cpp @@ -0,0 +1,58 @@ +// 1-indiziert. Array t: [4*n][4*m]. Nur die _x-Varianten aufrufen. +// Laufzeit: build: O(n*m), update, sum: O(log(n)*log(m)) +void build_y(int vx, int lx, int rx, int vy, int ly, int ry) { + if (ly == ry) { + if (lx == rx)vt[vx][vy] = a[lx][ly]; + else t[vx][vy] = t[vx*2][vy] + t[vx*2+1][vy]; + } else { + int my = (ly + ry) / 2; + build_y(vx, lx, rx, vy*2, ly, my); + build_y(vx, lx, rx, vy*2+1, my+1, ry); + t[vx][vy] = t[vx][vy*2] + t[vx][vy*2+1]; +}} + +void build_x(int vx = 1, int lx = 0, int rx = N-1) { + if (lx != rx) { + int mx = (lx + rx) / 2; + build_x(vx*2, lx, mx); + build_x(vx*2+1, mx+1, rx); + } + build_y(vx, lx, rx, 1, 0, m-1); +} + +int sum_y(int vx, int vy, int tly, int try_, int ly, int ry) { + if (ly > ry) return 0; + if (ly == tly && try_ == ry) return t[vx][vy]; + int tmy = (tly + try_) / 2; + return sum_y(vx, vy*2, tly, tmy, ly, min(ry,tmy)) + + sum_y(vx, vy*2+1, tmy+1, try_, max(ly,tmy+1), ry); +} + +int sum_x(int vx=1, int tlx=0, int trx=n-1,int lx,int rx,int ly,int ry) { + if (lx > rx) return 0; + if (lx == tlx && trx == rx) return sum_y(vx, 1, 0, m-1, ly, ry); + int tmx = (tlx + trx) / 2; + return sum_x(vx*2, tlx, tmx, lx, min(rx,tmx), ly, ry) + + sum_x(vx*2+1, tmx+1, trx, max(lx,tmx+1), rx, ly, ry); +} + +void update_y(int vx, int lx, int rx, int vy, int ly, int ry, + int x, int y, int new_val) { + if (ly == ry) { + if (lx == rx) t[vx][vy] = new_val; + else t[vx][vy] = t[vx*2][vy] + t[vx*2+1][vy]; + } else { + int my = (ly + ry) / 2; + if (y <= my) update_y(vx, lx, rx, vy*2, ly, my, x, y, new_val); + else update_y(vx, lx, rx, vy*2+1, my+1, ry, x, y, new_val); + t[vx][vy] = t[vx][vy*2] + t[vx][vy*2+1]; +}} + +void update_x(int vx=1, int lx=0, int rx=n-1, int x, int y, int new_val) { + if (lx != rx) { + int mx = (lx + rx) / 2; + if (x <= mx) update_x(vx*2, lx, mx, x, y, new_val); + else update_x(vx*2+1, mx+1, rx, x, y, new_val); + } + update_y(vx, lx, rx, 1, 0, m-1, x, y, new_val); +} diff --git a/datastructures/skewHeap.cpp b/datastructures/skewHeap.cpp new file mode 100644 index 0000000..ae2cc75 --- /dev/null +++ b/datastructures/skewHeap.cpp @@ -0,0 +1,29 @@ +// Skew Heap, verschmelzbare Priority Queue. +// Laufzeit: Merging, Inserting, DeleteMin: O(log(n)) amortisiert +struct node{ + int key; + node *lc, *rc; + node(int k) : key(k), lc(0), rc(0) {} +} *root = 0; +int size = 0; + +node* merge(node *x, node *y) { + if (!x) return y; + if (!y) return x; + if (x->key > y->key) swap(x,y); + x->rc = merge(x->rc, y); + swap(x->lc, x->rc); + return x; +} + +void insert(int x) { root = merge(root, new node(x)); size++; } + +int delmin() { + if (!root) return -1; + int ret = root->key; + node *troot = merge(root->lc, root->rc); + delete root; + root = troot; + size--; + return ret; +} diff --git a/datastructures/sparseTable.cpp b/datastructures/sparseTable.cpp new file mode 100644 index 0000000..52867de --- /dev/null +++ b/datastructures/sparseTable.cpp @@ -0,0 +1,27 @@ +struct SparseTable { + int st[MAX_N][MAX_LOG + 1], log[MAX_N + 1]; // Achtung: 2^MAX_LOG > MAX_N + vector<int> *a; + + // Funktion muss idempotent sein! Hier Minimum. + bool better(int lidx, int ridx) { return a->at(lidx) <= a->at(ridx); } + + void init(vector<int> *vec) { + a = vec; + for (int i = 0; i < (int)a->size(); i++) st[i][0] = i; + for (int j = 1; j <= MAX_LOG; j++) { + for (int i = 0; i + (1 << j) <= (int)a->size(); i++) { + st[i][j] = better(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]) + ? st[i][j - 1] : st[i + (1 << (j - 1))][j - 1]; + }} + + log[1] = 0; + for (int i = 2; i <= MAX_N; i++) log[i] = log[i/2] + 1; + } + + // Gibt Index des Ergebnisses in [l,r]. Laufzeit: O(1) + int queryIdempotent(int l, int r) { + int j = log[r - l + 1]; + return better(st[l][j], st[r - (1 << j) + 1][j]) + ? st[l][j] : st[r - (1 << j) + 1][j]; + } +}; diff --git a/datastructures/unionFind2.cpp b/datastructures/unionFind2.cpp deleted file mode 100644 index b26ec75..0000000 --- a/datastructures/unionFind2.cpp +++ /dev/null @@ -1,27 +0,0 @@ -vector<int> uf; - -init(int N) { - uf.assign(N,-1); //-1 indicates that every subset has size 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]; -} - -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 unionSets(int i, int j) { - if(findSet(i) != findSet(j)) linkSets(findSet(i),findSet(j)); -} - - |