summaryrefslogtreecommitdiff
path: root/datastructures
diff options
context:
space:
mode:
Diffstat (limited to 'datastructures')
-rw-r--r--datastructures/LCT.cpp2
-rw-r--r--datastructures/bitset.cpp11
-rw-r--r--datastructures/datastructures.tex125
-rw-r--r--datastructures/monotonicConvexHull.cpp3
-rw-r--r--datastructures/persistent.cpp5
-rw-r--r--datastructures/persistentArray.cpp8
-rw-r--r--datastructures/stlPQ.cpp10
-rw-r--r--datastructures/stlTree.cpp9
-rw-r--r--datastructures/unionFind.cpp10
-rw-r--r--datastructures/waveletTree.cpp2
10 files changed, 88 insertions, 97 deletions
diff --git a/datastructures/LCT.cpp b/datastructures/LCT.cpp
index 9adae89..c1dd278 100644
--- a/datastructures/LCT.cpp
+++ b/datastructures/LCT.cpp
@@ -42,7 +42,7 @@ struct LCT {
bool isRoot() {
return !parent || (parent->left != this &&
- parent->right != this);
+ parent->right != this);
}
void push() {
diff --git a/datastructures/bitset.cpp b/datastructures/bitset.cpp
index 9f33a5b..242d821 100644
--- a/datastructures/bitset.cpp
+++ b/datastructures/bitset.cpp
@@ -1,7 +1,6 @@
bitset<10> bits(0b000010100);
-cout << bits._Find_first() << endl; //2
-cout << bits._Find_next(2) << endl; //4
-cout << bits._Find_next(4) << endl; //10 bzw. N
-bits[x] = 1; //not bits.set(x)!
-bits[x] = 0; //not bits.reset(x)!
-bits[x].flip(); //not bits.flip(x)!
+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)!
diff --git a/datastructures/datastructures.tex b/datastructures/datastructures.tex
index 200144c..8f9698c 100644
--- a/datastructures/datastructures.tex
+++ b/datastructures/datastructures.tex
@@ -1,15 +1,5 @@
\section{Datenstrukturen}
-\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}
-
\begin{algorithm}{Segmentbaum}
\begin{methods}
\method{init}{baut den Baum auf}{n}
@@ -20,15 +10,10 @@
\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}{STL-Bitset}
- \sourcecode{datastructures/bitset.cpp}
-\end{algorithm}
-\clearpage
-
\begin{algorithm}{Fenwick Tree}
\begin{methods}
\method{init}{baut den Baum auf}{n\*\log(n)}
@@ -44,21 +29,10 @@
\end{methods}
\sourcecode{datastructures/fenwickTree2.cpp}
\end{algorithm}
+\clearpage
-\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}[optional]{Erste unbenutzte natürliche Zahl}
- \begin{methods}
- \method{get\_first\_unused}{findet kleinste unbenutzte Zahl}{\log(n)}
- \end{methods}
- \sourcecode{datastructures/firstUnused.cpp}
+\begin{algorithm}{STL-Rope (Implicit Cartesian Tree)}
+ \sourcecode{datastructures/stlRope.cpp}
\end{algorithm}
\begin{algorithm}{(Implicit) Treap (Cartesian Tree)}
@@ -69,15 +43,6 @@
\sourcecode{datastructures/treap2.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}
-
-\needspace{5\baselineskip}%
\begin{algorithm}{Range Minimum Query}
\begin{methods}
\method{init}{baut Struktur auf}{n\*\log(n)}
@@ -89,32 +54,19 @@
\sourcecode{datastructures/sparseTable.cpp}
\end{algorithm}
-\begin{algorithm}{STL-Tree}
- \sourcecode{datastructures/stlTree.cpp}
-\end{algorithm}
-
-\begin{algorithm}{STL-Rope (Implicit Cartesian Tree)}
- \sourcecode{datastructures/stlRope.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}{STL Priority Queue}
- Nicht notwendig, wenn Smaller-Larger-Optimization greift.
- \sourcecode{datastructures/stlPQ.cpp}
+\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}{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}
+\begin{algorithm}{STL-Bitset}
+ \sourcecode{datastructures/bitset.cpp}
\end{algorithm}
-\clearpage
-
\begin{algorithm}{Link-Cut-Tree}
\begin{methods}
\method{Constructor}{baut Wald auf}{n}
@@ -127,8 +79,25 @@
\end{methods}
\sourcecode{datastructures/LCT.cpp}
\end{algorithm}
-
\clearpage
+
+\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}
+
+\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}
+ \columnbreak
+ \sourcecode{datastructures/dynamicConvexHull.cpp}
+\end{algorithm}
+
\begin{algorithm}{Persistent}
\begin{methods}
\method{get}{berechnet Wert zu Zeitpunkt $t$}{\log(t)}
@@ -138,3 +107,35 @@
\sourcecode{datastructures/persistent.cpp}
\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]{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)}
+ \end{methods}
+ \sourcecode{datastructures/firstUnused.cpp}
+\end{algorithm}
+
diff --git a/datastructures/monotonicConvexHull.cpp b/datastructures/monotonicConvexHull.cpp
index 4b3dbff..0049b3d 100644
--- a/datastructures/monotonicConvexHull.cpp
+++ b/datastructures/monotonicConvexHull.cpp
@@ -1,6 +1,7 @@
// Lower Envelope mit MONOTONEN Inserts und Queries. Jede neue
// Gerade hat kleinere Steigung als alle vorherigen.
-vector<ll> ms, bs; int ptr = 0;
+vector<ll> ms, bs;
+int ptr = 0;
bool bad(int l1, int l2, int l3) {
return (bs[l3]-bs[l1])*(ms[l1]-ms[l2]) <
diff --git a/datastructures/persistent.cpp b/datastructures/persistent.cpp
index 1704ff2..0a65a79 100644
--- a/datastructures/persistent.cpp
+++ b/datastructures/persistent.cpp
@@ -7,12 +7,11 @@ struct persistent {
: time(time), data(1, {time, value}) {}
T get(int t) {
- return prev(upper_bound(all(data),
- pair<int, T>(t+1, {})))->second;
+ return prev(upper_bound(all(data), {t+1, {}}))->second;
}
int set(T value) {
- time+=2;
+ time += 2;
data.push_back({time, value});
return time;
}
diff --git a/datastructures/persistentArray.cpp b/datastructures/persistentArray.cpp
index 2db0e73..60d8b17 100644
--- a/datastructures/persistentArray.cpp
+++ b/datastructures/persistentArray.cpp
@@ -1,15 +1,13 @@
template<typename T>
-struct persistentArray{
- int time = 0;
+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);
- }
+ T get(int p, int t) {return data[p].get(t);}
int set(int p, T value) {
mods.push_back({p, time});
diff --git a/datastructures/stlPQ.cpp b/datastructures/stlPQ.cpp
index b48223b..4e439f8 100644
--- a/datastructures/stlPQ.cpp
+++ b/datastructures/stlPQ.cpp
@@ -5,11 +5,11 @@ using priorityQueue = __gnu_pbds::priority_queue<T, less<T>>;
int main() {
priorityQueue<int> pq;
- auto it = pq.push(5); // O(1)
+ 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
+ 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)
+ pq.join(pq2); // O(1)
}
diff --git a/datastructures/stlTree.cpp b/datastructures/stlTree.cpp
index 0fdc480..fbb68b9 100644
--- a/datastructures/stlTree.cpp
+++ b/datastructures/stlTree.cpp
@@ -7,10 +7,7 @@ using Tree = tree<T, null_type, less<T>, rb_tree_tag,
int main() {
Tree<int> X;
- // insert {1, 2, 4, 8, 16}
- for (int i = 1; i <= 16; i *= 2) X.insert(i);
- cout << *X.find_by_order(3) << endl; // => 8
- cout << X.order_of_key(10) << endl;
- // => 4 = min i, mit X[i] >= 10
- return 0;
+ 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/unionFind.cpp b/datastructures/unionFind.cpp
index 03ff63e..35843cd 100644
--- a/datastructures/unionFind.cpp
+++ b/datastructures/unionFind.cpp
@@ -12,12 +12,10 @@ int findSet(int n) { // Pfadkompression
}
void linkSets(int a, int b) { // Union by rank.
- if (unions[a] > unions[b]) unions[a] = b;
- else if (unions[b] > unions[a]) unions[b] = a;
- else {
- unions[a] = b;
- unions[b]--;
-}}
+ if (unions[b] > unions[a]) swap(a, b);
+ if (unions[b] == unions[a]) unions[b]--;
+ unions[a] = b;
+}
void unionSets(int a, int b) { // Diese Funktion aufrufen.
if (findSet(a) != findSet(b)) linkSets(findSet(a), findSet(b));
diff --git a/datastructures/waveletTree.cpp b/datastructures/waveletTree.cpp
index 8a0e10f..36c1b56 100644
--- a/datastructures/waveletTree.cpp
+++ b/datastructures/waveletTree.cpp
@@ -3,7 +3,6 @@ struct WaveletTree {
WaveletTree *ln, *rn;
ll lo, hi;
vector<int> b;
-
private:
WaveletTree(it from, it to, ll x, ll y)
: ln(nullptr), rn(nullptr), lo(x), hi(y), b(1) {
@@ -17,7 +16,6 @@ private:
ln = new WaveletTree(from, pivot, lo, mid);
rn = new WaveletTree(pivot, to, mid, hi);
}
-
public:
WaveletTree(vector<ll> in) : WaveletTree(all(in),
*min_element(all(in)), *max_element(all(in)) + 1){}
generated by cgit v1.2.3 (git 2.39.1) at 2025-12-23 23:11:09 +0000