summaryrefslogtreecommitdiff
path: root/datastructures
diff options
context:
space:
mode:
Diffstat (limited to 'datastructures')
-rw-r--r--datastructures/datastructures.tex82
-rw-r--r--datastructures/lichao.cpp76
-rw-r--r--datastructures/pbds.cpp27
-rw-r--r--datastructures/stlHashMap.cpp17
-rw-r--r--datastructures/stlPQ.cpp15
-rw-r--r--datastructures/stlTree.cpp13
6 files changed, 100 insertions, 130 deletions
diff --git a/datastructures/datastructures.tex b/datastructures/datastructures.tex
index 0285490..131a32f 100644
--- a/datastructures/datastructures.tex
+++ b/datastructures/datastructures.tex
@@ -14,6 +14,15 @@
\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)}
+ \end{methods}
+ \sourcecode{datastructures/waveletTree.cpp}
+\end{algorithm}
+
\begin{algorithm}{Fenwick Tree}
\begin{methods}
\method{init}{baut den Baum auf}{n\*\log(n)}
@@ -29,11 +38,11 @@
\end{methods}
\sourcecode{datastructures/fenwickTree2.cpp}
\end{algorithm}
-\columnbreak
\begin{algorithm}{STL-Rope (Implicit Cartesian Tree)}
\sourcecode{datastructures/stlRope.cpp}
\end{algorithm}
+\columnbreak
\begin{algorithm}{(Implicit) Treap (Cartesian Tree)}
\begin{methods}
@@ -62,15 +71,6 @@
\sourcecode{datastructures/sparseTableDisjoint.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)}
- \end{methods}
- \sourcecode{datastructures/waveletTree.cpp}
-\end{algorithm}
-
\begin{algorithm}{STL-Bitset}
\sourcecode{datastructures/bitset.cpp}
\end{algorithm}
@@ -89,6 +89,29 @@
\end{algorithm}
\columnbreak
+\begin{algorithm}{Policy Based Data Structures}
+ \sourcecode{datastructures/pbds.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}
+ \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}
+ \sourcecode{datastructures/lichao.cpp}
+\end{algorithm}
+
\begin{algorithm}{Union-Find}
\begin{methods}
\method{init}{legt $n$ einzelne Unions an}{n}
@@ -109,28 +132,7 @@
\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}
+\columnbreak
\begin{algorithm}{Persistent}
\begin{methods}
@@ -139,28 +141,12 @@
\method{reset}{setzt die Datenstruktur auf Zeitpunkt $t$}{1}
\end{methods}
\sourcecode{datastructures/persistent.cpp}
- \columnbreak
\sourcecode{datastructures/persistentArray.cpp}
\end{algorithm}
-\begin{algorithm}{STL-Tree}
- \sourcecode{datastructures/stlTree.cpp}
-\end{algorithm}
-
-\begin{algorithm}{STL Priority Queue}
- Nicht notwendig, wenn Smaller-Larger-Optimization greift.
- \sourcecode{datastructures/stlPQ.cpp}
-\end{algorithm}
-
-\begin{algorithm}{STL HashMap}
- 3 bis 4 mal langsamer als \code{std::vector} aber 8 bis 9 mal schneller als \code{std::map}
- \sourcecode{datastructures/stlHashMap.cpp}
-\end{algorithm}
-
\begin{algorithm}[optional]{Erste unbenutzte natürliche Zahl}
\begin{methods}
\method{get\_first\_unused}{findet kleinste unbenutzte Zahl}{\log(n)}
\end{methods}
\sourcecode{datastructures/firstUnused.cpp}
\end{algorithm}
-
diff --git a/datastructures/lichao.cpp b/datastructures/lichao.cpp
index e12d243..f66778e 100644
--- a/datastructures/lichao.cpp
+++ b/datastructures/lichao.cpp
@@ -1,44 +1,46 @@
-vector<ll> xs; // IMPORTANT: Initialize before constructing Lichao!
-int findX(int i) {return distance(xs.begin(), lower_bound(all(xs), i));}
+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 it to needed function type.
- ll m, c;
- ll operator()(int x) {return m*xs[x] + c;}
+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);}
+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);
- }
+ 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));}
+ 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/datastructures/pbds.cpp b/datastructures/pbds.cpp
new file mode 100644
index 0000000..a0e5383
--- /dev/null
+++ b/datastructures/pbds.cpp
@@ -0,0 +1,27 @@
+#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
+auto it = T.find_by_order(k); // k-th element
+
+template<typename T>
+struct chash {
+ 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/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/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
-}
generated by cgit v1.2.3 (git 2.39.1) at 2025-12-23 23:11:15 +0000