merge mzuenni

8 files changed, 55 insertions, 31 deletions

diff --git a/content/datastructures/LCT.cpp b/content/datastructures/LCT.cpp
index c1dd278..e88c8d3 100644
--- a/content/datastructures/LCT.cpp
+++ b/content/datastructures/LCT.cpp
@@ -53,8 +53,7 @@ struct LCT {
 				if (right) right->revert ^= 1;
 			}
 			nodeValue = joinValueDelta(nodeValue, delta);
-			subTreeValue = joinValueDelta(subTreeValue,
-			                              _update(delta, size));
+			subTreeValue = getSubtreeValue();
 			if (left) left->delta = joinDeltas(left->delta, delta);
 			if (right) right->delta = joinDeltas(right->delta, delta);
 			delta = updateDefault;
@@ -68,8 +67,8 @@ struct LCT {
 			subTreeValue = joinValueDelta(nodeValue, delta);
 			size = 1;
 			if (left) {
-				subTreeValue = _query(subTreeValue,
-				                      left->getSubtreeValue());
+				subTreeValue = _query(left->getSubtreeValue(),
+				                      subTreeValue);
 				size += left->size;
 			}
 			if (right) {
diff --git a/content/graph/bitonicTSP.cpp b/content/graph/bitonicTSP.cpp
index eeff156..b42f089 100644
--- a/content/graph/bitonicTSP.cpp
+++ b/content/graph/bitonicTSP.cpp
@@ -1,6 +1,6 @@
 vector<vector<double>> dist; // Initialisiere mit Entfernungen zwischen Punkten.
 
-auto bitonicTSP() {
+auto bitonicTSP() { // n >= 2
 	vector<double> dp(ssize(dist), HUGE_VAL);
 	vector<int> pre(ssize(dist)); // nur für Tour
 	dp[0] = 0; dp[1] = 2 * dist[0][1]; pre[1] = 0;
diff --git a/content/graph/bronKerbosch.cpp b/content/graph/bronKerbosch.cpp
index cf07c88..144707a 100644
--- a/content/graph/bronKerbosch.cpp
+++ b/content/graph/bronKerbosch.cpp
@@ -9,7 +9,7 @@ void bronKerboschRec(bits R, bits P, bits X) {
 	if (P.none() && X.none()) {
 		cliques.push_back(R);
 	} else {
-		int q = min(P._Find_first(), X._Find_first());
+		int q = (P | X)._Find_first();
 		bits cands = P & ~adj[q];
 		for (int i = 0; i < ssize(adj); i++) if (cands[i]) {
 			R[i] = 1;
diff --git a/content/math/math.tex b/content/math/math.tex
index 943beef..bcb4275 100644
--- a/content/math/math.tex
+++ b/content/math/math.tex
@@ -414,7 +414,8 @@ so gilt
 	\sourcecode{math/binomial3.cpp}

 %\end{algorithm}

 

-\paragraph{\textsc{Catalan}-Zahlen}

+\paragraph{\textsc{Catalan}-Zahlen:}

+$1,~1,~2,~5,~14,~42,~132,~429,~1430,~4862,~16796,~58786,~208012,~742900$

 \begin{itemize}

 	\item Die \textsc{Catalan}-Zahl $C_n$ gibt an:

 	\begin{itemize}

@@ -429,18 +430,19 @@ so gilt
 \[C_0 = 1\qquad C_n = \sum\limits_{k = 0}^{n - 1} C_kC_{n - 1 - k} =

 \frac{1}{n + 1}\binom{2n}{n} = \frac{4n - 2}{n+1} C_{n-1} \sim \frac{4^n}{n^{3/2} \sqrt{\pi}}\]

 \begin{itemize}

-	\item Formel $1$ erlaubt Berechnung ohne Division in \runtime{n^2}

-	\item Formel $2$ und $3$ erlauben Berechnung in \runtime{n}

+	\item Formel $1$ ohne Division in \runtime{n^2}, Formel $2$ und $3$ in \runtime{n}

 \end{itemize}

 

 \paragraph{\textsc{Catalan}-Convolution}

 \begin{itemize}

-	\item Anzahl an Klammerausdrücken mit $n+k$ Klammerpaaren, die mit $(^k$ beginnen.

+	\item Anzahl an Klammerausdrücken mit $n+k$ Klammerpaaren, die mit $\texttt{(}^k$ beginnen.

 \end{itemize}

 \[C^k_0 = 1\qquad C^k_n = \sum\limits_{\mathclap{a_0+a_1+\dots+a_k=n}} C_{a_0}C_{a_1}\cdots C_{a_k} =

 \frac{k+1}{n+k+1}\binom{2n+k}{n} = \frac{(2n+k-1)(2n+k)}{n(n+k+1)} C_{n-1}\]

 

-\paragraph{\textsc{Euler}-Zahlen}

+\paragraph{\textsc{Euler}-Zahlen:}

+$|~1~|~1~|~1,~1~|~1,~4,~1~|~1,~11,~11,~1~|~1,~26,~66,~26,~1~|$

+

 Die Anzahl der Permutationen von $\{1, \ldots, n\}$ mit genau $k$ Anstiegen.

 Für die $n$-te Zahl gibt es $n$ mögliche Positionen zum Einfügen.

 Dabei wird entweder ein Anstieg in zwei gesplitted oder ein Anstieg um $n$ ergänzt.

@@ -452,11 +454,13 @@ Dabei wird entweder ein Anstieg in zwei gesplitted oder ein Anstieg um $n$ ergä
 	\left(\sum_{i=0}^\infty (-1)^i \binom{n+1}{i} x^i\right)

 \]

 

-\paragraph{\textsc{Stirling}-Zahlen 1. Art}

+\paragraph{\textsc{Stirling}-Zahlen 1. Art:}

+$|~1~|~0,~1~|~0,~1,~1~|~0,~2,~3,~1~|~0,~6,~11,~6,~1~|$

+

 Die Anzahl der Permutationen von $\{1, \ldots, n\}$ mit genau $k$ Zyklen.

 Es gibt zwei Möglichkeiten für die $n$-te Zahl. Entweder sie bildet einen eigenen Zyklus, oder sie kann an jeder Position in jedem Zyklus einsortiert werden.

 \[\stirlingI{0}{0} = 1 \qquad

-\stirlingI{n}{0} = \stirlingI{0}{n} = 0 \qquad

+\stirlingI{n}{0} = \stirlingI{0}{k} = 0 \qquad

 \stirlingI{n}{k} = \stirlingI{n-1}{k-1} + (n-1) \stirlingI{n-1}{k}\]

 \[

 \stirlingI{n}{k}

@@ -464,7 +468,9 @@ Es gibt zwei Möglichkeiten für die $n$-te Zahl. Entweder sie bildet einen eige
 = n! [x^{n-k}] \frac{1}{k!} \left(\sum_{i=0}^\infty \frac{1}{i+1}x^i\right)^k

 \]

 

-\paragraph{\textsc{Stirling}-Zahlen 2. Art}

+\paragraph{\textsc{Stirling}-Zahlen 2. Art:}

+$|~1~|~0,~1~|~0,~1,~1~|~0,~1,~3,~1~|~0,~1,~7,~6,~1~|$

+

 Die Anzahl der Möglichkeiten $n$ Elemente in $k$ nichtleere Teilmengen zu zerlegen.

 Es gibt $k$ Möglichkeiten die $n$ in eine $n-1$-Partition einzuordnen.

 Dazu kommt der Fall, dass die $n$ in ihrer eigenen Teilmenge (alleine) steht.

@@ -479,7 +485,9 @@ Dazu kommt der Fall, dass die $n$ in ihrer eigenen Teilmenge (alleine) steht.
 = n! [x^{n-k}] \frac{1}{k!} \left(\sum_{i=0}^\infty \frac{1}{(i+1)!}x^i\right)^k

 \]

 

-\paragraph{\textsc{Bell}-Zahlen}

+\paragraph{\textsc{Bell}-Zahlen:}

+$1,~1,~2,~5,~15,~52,~203,~877,~4140,~21147,~115975,~678570,~4213597$

+

 Anzahl der Partitionen von $\{1, \ldots, n\}$.

 Wie \textsc{Stirling}-Zahlen 2. Art ohne Limit durch $k$.

 \[B_1 = 1 \qquad

@@ -489,12 +497,20 @@ B_n = \sum\limits_{k = 0}^{n - 1} B_k\binom{n-1}{k}
 \qquad

 B_{p^m+n}\equiv m\cdot B_n + B_{n+1} \bmod{p}\]

 

-\paragraph{Partitions}

+\paragraph{$\boldsymbol{k}$ Partitions:}

+$|~1~|~0,~1~|~0,~1,~1~|~0,~1,~1,~1~|~0,~1,~2,~1,~1~|~0,~1,~2,~2,~1,~1~|~0,~1,~3,~3,~2,~1,~1~|$

+

 Die Anzahl der Partitionen von $n$ in genau $k$ positive Summanden.

-Die Anzahl der Partitionen von $n$ mit Elementen aus ${1,\dots,k}$.

+Die Anzahl der Partitionen von $n$ mit größtem Elementen $k$.

 \begin{align*}

 	p_0(0)=1 \qquad p_k(n)&=0 \text{ für } k > n \text{ oder } n \leq 0 \text{ oder } k \leq 0\\

 	p_k(n)&= p_k(n-k) + p_{k-1}(n-1)\\

+\end{align*}

+

+\paragraph{Partitions:}

+$1,~1,~2,~3,~5,~7,~11,~15,~22,~30,~42,~56,~77,~101,~135,~176,~231,~297,~385,~490,~627$

+

+\begin{align*}

 	p(n)=\sum_{k=1}^{n} p_k(n)&=p_n(2n)=\sum\limits_{k=1}^\infty(-1)^{k+1}\bigg[p\bigg(n - \frac{k(3k-1)}{2}\bigg) + p\bigg(n - \frac{k(3k+1)}{2}\bigg)\bigg] \\

 	p(n)&=[x^n] \left(\sum_{k=-\infty}^\infty (-1)^k x^{k(3k-1)/2}\right)^{-1}

 	  \sim \frac{1}{4 \sqrt{3} n} \exp\left(\pi \sqrt{\frac{2n}{3}}\right)

diff --git a/content/math/piLehmer.cpp b/content/math/piLehmer.cpp
index 17df85e..adef16d 100644
--- a/content/math/piLehmer.cpp
+++ b/content/math/piLehmer.cpp
@@ -6,7 +6,7 @@ ll memoC[N];
 

 void init() {

 	primeSieve(); // @\sourceref{math/primeSieve.cpp}@

-	for (ll i = 0; i < N; i++) {

+	for (ll i = 1; i < N; i++) {

 		memoC[i] = memoC[i - 1];

 		if (isPrime(i)) memoC[i]++;

 	}

diff --git a/content/math/transforms/seriesOperations.cpp b/content/math/transforms/seriesOperations.cpp
index 3d8aa11..cfac7b9 100644
--- a/content/math/transforms/seriesOperations.cpp
+++ b/content/math/transforms/seriesOperations.cpp
@@ -1,4 +1,4 @@
-vector<ll> poly_inv(const vector<ll>& a, int n) {
+vector<ll> poly_inv(const vector<ll>& a, int n) { // a[0] == 1
 	vector<ll> q = {powMod(a[0], mod-2, mod)};
 	for (int len = 1; len < n; len *= 2){
 		vector<ll> a2 = a, q2 = q;
@@ -35,13 +35,13 @@ vector<ll> poly_integr(vector<ll> a) {
 	return a;
 }
 
-vector<ll> poly_log(vector<ll> a, int n) {
+vector<ll> poly_log(vector<ll> a, int n) { // a[0] == 1
 	a = mul(poly_deriv(a), poly_inv(a, n));
 	a.resize(n-1);
 	return poly_integr(a);
 }
 
-vector<ll> poly_exp(vector<ll> a, int n) {
+vector<ll> poly_exp(vector<ll> a, int n) { // a[0] == 0
 	vector<ll> q = {1};
 	for (int len = 1; len < n; len *= 2) {
 		vector<ll> p = poly_log(q, 2*len);
diff --git a/content/other/other.tex b/content/other/other.tex
index 9661d89..d8726d4 100644
--- a/content/other/other.tex
+++ b/content/other/other.tex
@@ -151,7 +151,7 @@
 	Das Komplement eines Vertex-Cover ist ein Independent Set.

 	$\Rightarrow$ Max Weight Independent Set ist Komplement von Min Weight Vertex Cover.

 

-	\item \textbf{Bipartiter Graph:}

+	\item \textbf{Bipartiter Graph (Satz von \textsc{König}):}

 	Min Vertex Cover (kleinste Menge Knoten, die alle Kanten berühren) = Max Matching.

 	Richte Kanten im Matching von $B$ nach $A$ und sonst von $A$ nach $B$, markiere alle Knoten die von einem ungematchten Knoten in $A$ erreichbar sind, das Vertex Cover sind die markierten Knoten aus $B$ und die unmarkierten Knoten aus $A$.

 

@@ -186,15 +186,19 @@
 	\item \textbf{\textsc{Bertrand}sches Postulat:}

 	Für alle $n \in \mathbb{N}$ gilt: Ex existiert eine Primzahl $p$ mit $n < p \leq 2n$.

 

-	\item \textbf{Satz von \textsc{Kirchhoff}:}

+	\item \textbf{Satz von \textsc{Kirchhoff} (Anzahl Spannbäume):}

 	Sei $G$ ein zusammenhängender, ungerichteter Graph evtl. mit Mehrfachkanten.

-	Sei $A$ die Adjazenzmatrix von $G$.

+	Sei $A$ die Adjazenzmatrix von~$G$.

 	Dabei ist $a_{ij}$ die Anzahl der Kanten zwischen Knoten $i$ und $j$.

-	Sei $B$ eine Diagonalmatrix, $b_{ii}$ sei der Grad von Knoten $i$.

+	Sei $B$ eine Diagonalmatrix mit $b_{ii}$ Grad von Knoten $i$.

 	Definiere $R = B - A$.

-	Alle Kofaktoren von $R$ sind gleich und die Anzahl der Spannbäume von $G$.

+	Entferne $k$-te Zeile und $k$-te Spalte ($k$ beliebig) und berechne Betrag der Determinante.

+	Das Ergebnis ist die Anzahl der Spannbäume von $G$.

 	\newline

-	Entferne letzte Zeile und Spalte und berechne Betrag der Determinante.

+	Funktioniert auch für gerichtete Graphen: $b_{ii}$ ist der Outdegree und man

+	berechnet die Determinante nach Entfernen der $k$-ten Zeile und Spalte.

+	Das Ergebnis ist die Anzahl an gerichteten Spannbäumen mit Wurzel $k$,

+	sodass jeder Knoten einen Pfad zu $k$ hat.

 

 	\item \textbf{\textsc{Dilworth}'s Theorem:}

 	Sei $S$ eine Menge und $\leq$ eine partielle Ordnung ($S$ ist ein Poset).

@@ -205,10 +209,15 @@
 	Es gilt: Die Größe der längsten Antikette gleicht der Größe der kleinsten Partition.

 	$\Rightarrow$ \emph{Weite} des Poset.

 	\newline

-	Berechnung: Maximales Matching in bipartitem Graphen.

+	Berechnung der minimalen Partition: Maximales Matching in bipartitem Graphen.

 	Dupliziere jedes $s \in S$ in $u_s$ und $v_s$.

 	Falls $x \leq y$, füge Kante $u_x \to v_y$ hinzu.

-	Wenn Matching zu langsam ist, versuche Struktur des Posets auszunutzen und evtl. anders eine maximale Antikette zu finden.

+	Wenn $u_x$ mit $v_y$ gematched wird, sind $x$ und $y$ in derselben Kette.

+	\newline

+	Berechnung der maximalen Antikette: Verwende Satz von König, um ein

+	minimales Vertexcover des bipartiten Graphen zu finden.

+	Ersetze $u_x, v_x$ durch $x$ und erhalte so minimales Vertexcover vom Poset.

+	Das Komplement davon ist eine maximale Antikette.

 	

 	\item \textbf{\textsc{Tur\'an}'s Theorem:}

 	Die Anzahl an Kanten in einem Graphen mit $n$ Knoten der keine clique der größe $x+1$ enthält ist:

diff --git a/content/string/trie.cpp b/content/string/trie.cpp
index db39c43..64d7beb 100644
--- a/content/string/trie.cpp
+++ b/content/string/trie.cpp
@@ -10,13 +10,14 @@ vector<node> trie = {node()};
 int traverse(const vector<int>& word, int x) {
 	int id = 0;
 	for (int c : word) {
-		if (id < 0 || (trie[id].words == 0 && x <= 0)) return -1;
+		if (trie[id].words == 0 && x <= 0) return -1;
 		trie[id].words += x;
 		if (trie[id].nxt[c] < 0 && x > 0) {
 			trie[id].nxt[c] = ssize(trie);
 			trie.emplace_back();
 		}
 		id = trie[id].nxt[c];
+		if (id < 0) return -1;
 	}
 	trie[id].words += x;
 	trie[id].ends += x;
@@ -26,7 +27,6 @@ int traverse(const vector<int>& word, int x) {
 int insert(const vector<int>& word) {
 	return traverse(word, 1);
 }
-
 bool erase(const vector<int>& word) {
 	int id = traverse(word, 0);
 	if (id < 0 || trie[id].ends <= 0) return false;