summaryrefslogtreecommitdiff
path: root/datastructures
diff options
context:
space:
mode:
Diffstat (limited to 'datastructures')
-rw-r--r--datastructures/RMQ.cpp27
-rw-r--r--datastructures/datastructures.tex57
-rw-r--r--datastructures/dynamicConvexHull.cpp10
-rw-r--r--datastructures/fenwickTree.cpp2
-rw-r--r--datastructures/fenwickTree2.cpp2
-rw-r--r--datastructures/monotonicConvexHull.cpp43
-rw-r--r--datastructures/persistent.cpp2
-rw-r--r--datastructures/test/fenwickTree.cpp26
-rw-r--r--datastructures/test/fenwickTree2.cpp28
-rw-r--r--datastructures/test/monotonicConvexHull.cpp26
-rw-r--r--datastructures/test/persistent.cpp10
-rw-r--r--datastructures/unionFind2.cpp33
12 files changed, 176 insertions, 90 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 4139219..0285490 100644
--- a/datastructures/datastructures.tex
+++ b/datastructures/datastructures.tex
@@ -17,19 +17,19 @@
\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{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}
-\clearpage
+\columnbreak
\begin{algorithm}{STL-Rope (Implicit Cartesian Tree)}
\sourcecode{datastructures/stlRope.cpp}
@@ -54,6 +54,14 @@
\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}{Wavelet Tree}
\begin{methods}
\method{Constructor}{baut den Baum auf}{n\*\log(n)}
@@ -79,7 +87,7 @@
\end{methods}
\sourcecode{datastructures/LCT.cpp}
\end{algorithm}
-\clearpage
+\columnbreak
\begin{algorithm}{Union-Find}
\begin{methods}
@@ -91,11 +99,37 @@
\sourcecode{datastructures/unionFind.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}[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}
+
+\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}
\columnbreak
+ \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}
+ \optional{
+ \subsubsection{Li Chao tree \opthint}
+ \sourcecode{datastructures/lichao.cpp}
+ }
\end{algorithm}
\begin{algorithm}{Persistent}
@@ -105,6 +139,7 @@
\method{reset}{setzt die Datenstruktur auf Zeitpunkt $t$}{1}
\end{methods}
\sourcecode{datastructures/persistent.cpp}
+ \columnbreak
\sourcecode{datastructures/persistentArray.cpp}
\end{algorithm}
@@ -122,16 +157,6 @@
\sourcecode{datastructures/stlHashMap.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..6c5ed91 100644
--- a/datastructures/fenwickTree.cpp
+++ b/datastructures/fenwickTree.cpp
@@ -10,6 +10,6 @@ void init(int n) {
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..43c3a32 100644
--- a/datastructures/fenwickTree2.cpp
+++ b/datastructures/fenwickTree2.cpp
@@ -14,7 +14,7 @@ void init(vector<ll>& v) {
}
ll prefix_sum (int i) {
- ll res = 0; 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/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/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/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/monotonicConvexHull.cpp b/datastructures/test/monotonicConvexHull.cpp
new file mode 100644
index 0000000..62ea4cd
--- /dev/null
+++ b/datastructures/test/monotonicConvexHull.cpp
@@ -0,0 +1,26 @@
+#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..d98569b
--- /dev/null
+++ b/datastructures/test/persistent.cpp
@@ -0,0 +1,10 @@
+#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/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)];
}
generated by cgit v1.2.3 (git 2.39.1) at 2025-12-24 06:00:54 +0000