Range Minimum Query - Versionsgeschichte

Phzh: Form, typo

2025-02-11T19:06:02Z

Form, typo

2003:F9:5F00:DA00:E598:316C:FC9E:BCDB: ISBN von Google Books ersetzt durch ISBN aus DigiBib

2024-12-23T21:32:11Z

ISBN von Google Books ersetzt durch ISBN aus DigiBib

← Nächstältere Version		Version vom 23. Dezember 2024, 23:32 Uhr
Zeile 94:		Zeile 94:

	Aufgrund des Lemmas ergibt sich eine Reduktion für in-Block RMQs, da nicht jeder Block einzeln vorberechnet wird, sondern nur die Antworten für alle möglichen Kartesischen Bäume über <math>s</math> Elementen ausreichen, denn jeder Block lässt sich in Linearzeit (Johannes Fischer and Heun 2011)<ref name="10.1137/090779759"/> auf einen Kartesischen Baum abbilden, da die Baumkonstruktion amortisiert in <math>\mathcal{O}(n)</math> liegt. Die Anzahl der Bäume entspricht der Catalan-Zahl <math>\textstyle C_s = \frac{1}{s+1} \binom{2s}{s}</math>, und es existiert eine Bijektion zwischen allen kartesischen Bäumen auf <math>s</math> Knoten und den Zahlen <math>[1, C_s]</math>, die mittels einem Algorithmus in Linearzeit berechnet werden kann<ref>{{Literatur \|Autor=Donald E. Knuth \|Titel=Generating All Trees—		Aufgrund des Lemmas ergibt sich eine Reduktion für in-Block RMQs, da nicht jeder Block einzeln vorberechnet wird, sondern nur die Antworten für alle möglichen Kartesischen Bäume über <math>s</math> Elementen ausreichen, denn jeder Block lässt sich in Linearzeit (Johannes Fischer and Heun 2011)<ref name="10.1137/090779759"/> auf einen Kartesischen Baum abbilden, da die Baumkonstruktion amortisiert in <math>\mathcal{O}(n)</math> liegt. Die Anzahl der Bäume entspricht der Catalan-Zahl <math>\textstyle C_s = \frac{1}{s+1} \binom{2s}{s}</math>, und es existiert eine Bijektion zwischen allen kartesischen Bäumen auf <math>s</math> Knoten und den Zahlen <math>[1, C_s]</math>, die mittels einem Algorithmus in Linearzeit berechnet werden kann<ref>{{Literatur \|Autor=Donald E. Knuth \|Titel=Generating All Trees—
	History of Combinatorial Generation \|Hrsg= \|Sammelwerk=The Art of Computer Programming \|Band=Vol. 4 \|Nummer=Fasc. 4 \|Verlag=Addison-Wesley \|Ort=Upper Saddle River, NJ \|Datum=2006 \|ISBN=~~9780132702348~~ \|Seiten=4 ff.}}</ref>. Diese numerische Repräsentation eines kartesischen Baumes wird als ''Index'' für die vorberechnete in-Block Tabelle <math>P[1,C_s][1,s][1,s]</math> verwendet, und ihr Platzbedarf kann mittels [[Stirlingformel]] als <math>\log_2 C_s \approx 2s</math> Bits abgeschätzt werden.<br />		History of Combinatorial Generation \|Hrsg= \|Sammelwerk=The Art of Computer Programming \|Band=Vol. 4 \|Nummer=Fasc. 4 \|Verlag=Addison-Wesley \|Ort=Upper Saddle River, NJ \|Datum=2006 \|ISBN=9780321335708 \|Seiten=4 ff.}}</ref>. Diese numerische Repräsentation eines kartesischen Baumes wird als ''Index'' für die vorberechnete in-Block Tabelle <math>P[1,C_s][1,s][1,s]</math> verwendet, und ihr Platzbedarf kann mittels [[Stirlingformel]] als <math>\log_2 C_s \approx 2s</math> Bits abgeschätzt werden.<br />
	Insgesamt ergibt sich daraus ein Platzbedarf von <math>\|P\| = \mathcal{O}(2^{2s} \cdot s \cdot s) = \mathcal{O}(\sqrt{n}\,\log^2 n) = o(n)</math>.<br />		Insgesamt ergibt sich daraus ein Platzbedarf von <math>\|P\| = \mathcal{O}(2^{2s} \cdot s \cdot s) = \mathcal{O}(\sqrt{n}\,\log^2 n) = o(n)</math>.<br />

2003:F9:5F00:DA00:E598:316C:FC9E:BCDB: Falscher Index korrigier

2024-12-23T20:59:49Z

Falscher Index korrigier

← Nächstältere Version		Version vom 23. Dezember 2024, 22:59 Uhr
Zeile 93:		Zeile 93:
	Der interessierte Leser kann den Beweis des Lemmas in Johannes Fischer and Heun (2011, S. 472)<ref name="10.1137/090779759"/> nachlesen.		Der interessierte Leser kann den Beweis des Lemmas in Johannes Fischer and Heun (2011, S. 472)<ref name="10.1137/090779759"/> nachlesen.

	Aufgrund des Lemmas ergibt sich eine Reduktion für in-Block RMQs, da nicht jeder Block einzeln vorberechnet wird, sondern nur die Antworten für alle möglichen Kartesischen Bäume über <math>s</math> Elementen ausreichen, denn jeder Block lässt sich in Linearzeit (Johannes Fischer and Heun 2011)<ref name="10.1137/090779759"/> auf einen Kartesischen Baum abbilden, da die Baumkonstruktion amortisiert in <math>\mathcal{O}(n)</math> liegt. Die Anzahl der Bäume entspricht der Catalan-Zahl <math>\textstyle C_s = \frac{1}{s+1} \binom{2s}{s}</math>, und es existiert eine Bijektion zwischen allen kartesischen Bäumen auf <math>n</math> Knoten und den Zahlen <math>[1, C_s]</math>, die mittels einem Algorithmus in Linearzeit berechnet werden kann<ref>{{Literatur \|Autor=Donald E. Knuth \|Titel=Generating All Trees—		Aufgrund des Lemmas ergibt sich eine Reduktion für in-Block RMQs, da nicht jeder Block einzeln vorberechnet wird, sondern nur die Antworten für alle möglichen Kartesischen Bäume über <math>s</math> Elementen ausreichen, denn jeder Block lässt sich in Linearzeit (Johannes Fischer and Heun 2011)<ref name="10.1137/090779759"/> auf einen Kartesischen Baum abbilden, da die Baumkonstruktion amortisiert in <math>\mathcal{O}(n)</math> liegt. Die Anzahl der Bäume entspricht der Catalan-Zahl <math>\textstyle C_s = \frac{1}{s+1} \binom{2s}{s}</math>, und es existiert eine Bijektion zwischen allen kartesischen Bäumen auf <math>s</math> Knoten und den Zahlen <math>[1, C_s]</math>, die mittels einem Algorithmus in Linearzeit berechnet werden kann<ref>{{Literatur \|Autor=Donald E. Knuth \|Titel=Generating All Trees—
	History of Combinatorial Generation \|Hrsg= \|Sammelwerk=The Art of Computer Programming \|Band=Vol. 4 \|Nummer=Fasc. 4 \|Verlag=Addison-Wesley \|Ort=Upper Saddle River, NJ \|Datum=2006 \|ISBN=9780132702348 \|Seiten=4 ff.}}</ref>. Diese numerische Repräsentation eines kartesischen Baumes wird als ''Index'' für die vorberechnete in-Block Tabelle <math>P[1,C_s][1,s][1,s]</math> verwendet, und ihr Platzbedarf kann mittels [[Stirlingformel]] als <math>\log_2 C_s \approx 2s</math> Bits abgeschätzt werden.<br />		History of Combinatorial Generation \|Hrsg= \|Sammelwerk=The Art of Computer Programming \|Band=Vol. 4 \|Nummer=Fasc. 4 \|Verlag=Addison-Wesley \|Ort=Upper Saddle River, NJ \|Datum=2006 \|ISBN=9780132702348 \|Seiten=4 ff.}}</ref>. Diese numerische Repräsentation eines kartesischen Baumes wird als ''Index'' für die vorberechnete in-Block Tabelle <math>P[1,C_s][1,s][1,s]</math> verwendet, und ihr Platzbedarf kann mittels [[Stirlingformel]] als <math>\log_2 C_s \approx 2s</math> Bits abgeschätzt werden.<br />
	Insgesamt ergibt sich daraus ein Platzbedarf von <math>\|P\| = \mathcal{O}(2^{2s} \cdot s \cdot s) = \mathcal{O}(\sqrt{n}\,\log^2 n) = o(n)</math>.<br />		Insgesamt ergibt sich daraus ein Platzbedarf von <math>\|P\| = \mathcal{O}(2^{2s} \cdot s \cdot s) = \mathcal{O}(\sqrt{n}\,\log^2 n) = o(n)</math>.<br />

2003:F9:5F00:DA00:E598:316C:FC9E:BCDB: Konsistenteres Indexing

2024-12-23T20:55:41Z

Konsistenteres Indexing

← Nächstältere Version		Version vom 23. Dezember 2024, 22:55 Uhr
Zeile 93:		Zeile 93:
	Der interessierte Leser kann den Beweis des Lemmas in Johannes Fischer and Heun (2011, S. 472)<ref name="10.1137/090779759"/> nachlesen.		Der interessierte Leser kann den Beweis des Lemmas in Johannes Fischer and Heun (2011, S. 472)<ref name="10.1137/090779759"/> nachlesen.

	Aufgrund des Lemmas ergibt sich eine Reduktion für in-Block RMQs, da nicht jeder Block einzeln vorberechnet wird, sondern nur die Antworten für alle möglichen Kartesischen Bäume über <math>s</math> Elementen ausreichen, denn jeder Block lässt sich in Linearzeit (Johannes Fischer and Heun 2011)<ref name="10.1137/090779759"/> auf einen Kartesischen Baum abbilden, da die Baumkonstruktion amortisiert in <math>\mathcal{O}(n)</math> liegt. Die Anzahl der Bäume entspricht der Catalan-Zahl <math>\textstyle C_s = \frac{1}{s+1} \binom{2s}{s}</math>, und es existiert eine Bijektion zwischen allen kartesischen Bäumen auf <math>n</math> Knoten und den Zahlen <math>[0, C_s-1]</math>, die mittels einem Algorithmus in Linearzeit berechnet werden kann<ref>{{Literatur \|Autor=Donald E. Knuth \|Titel=Generating All Trees—		Aufgrund des Lemmas ergibt sich eine Reduktion für in-Block RMQs, da nicht jeder Block einzeln vorberechnet wird, sondern nur die Antworten für alle möglichen Kartesischen Bäume über <math>s</math> Elementen ausreichen, denn jeder Block lässt sich in Linearzeit (Johannes Fischer and Heun 2011)<ref name="10.1137/090779759"/> auf einen Kartesischen Baum abbilden, da die Baumkonstruktion amortisiert in <math>\mathcal{O}(n)</math> liegt. Die Anzahl der Bäume entspricht der Catalan-Zahl <math>\textstyle C_s = \frac{1}{s+1} \binom{2s}{s}</math>, und es existiert eine Bijektion zwischen allen kartesischen Bäumen auf <math>n</math> Knoten und den Zahlen <math>[1, C_s]</math>, die mittels einem Algorithmus in Linearzeit berechnet werden kann<ref>{{Literatur \|Autor=Donald E. Knuth \|Titel=Generating All Trees—
	History of Combinatorial Generation \|Hrsg= \|Sammelwerk=The Art of Computer Programming \|Band=Vol. 4 \|Nummer=Fasc. 4 \|Verlag=Addison-Wesley \|Ort=Upper Saddle River, NJ \|Datum=2006 \|ISBN=9780132702348 \|Seiten=4 ff.}}</ref>. Diese numerische Repräsentation eines kartesischen Baumes wird als ''Index'' für die vorberechnete in-Block Tabelle <math>P[1,C_s][1,s][1,s]</math> verwendet, und ihr Platzbedarf kann mittels [[Stirlingformel]] als <math>\log_2 C_s \approx 2s</math> Bits abgeschätzt werden.<br />		History of Combinatorial Generation \|Hrsg= \|Sammelwerk=The Art of Computer Programming \|Band=Vol. 4 \|Nummer=Fasc. 4 \|Verlag=Addison-Wesley \|Ort=Upper Saddle River, NJ \|Datum=2006 \|ISBN=9780132702348 \|Seiten=4 ff.}}</ref>. Diese numerische Repräsentation eines kartesischen Baumes wird als ''Index'' für die vorberechnete in-Block Tabelle <math>P[1,C_s][1,s][1,s]</math> verwendet, und ihr Platzbedarf kann mittels [[Stirlingformel]] als <math>\log_2 C_s \approx 2s</math> Bits abgeschätzt werden.<br />
	Insgesamt ergibt sich daraus ein Platzbedarf von <math>\|P\| = \mathcal{O}(2^{2s} \cdot s \cdot s) = \mathcal{O}(\sqrt{n}\,\log^2 n) = o(n)</math>.<br />		Insgesamt ergibt sich daraus ein Platzbedarf von <math>\|P\| = \mathcal{O}(2^{2s} \cdot s \cdot s) = \mathcal{O}(\sqrt{n}\,\log^2 n) = o(n)</math>.<br />

2003:F9:5F00:DA00:E598:316C:FC9E:BCDB: LOUDS eignet sich nichts zur Rekonstruktion von Kartesischen Bäumen, stattdessen muss man die Bijektion aus dem ursprünglichen Paper von Fischer und Heun verwenden.

2024-12-23T20:53:07Z

LOUDS eignet sich nichts zur Rekonstruktion von Kartesischen Bäumen, stattdessen muss man die Bijektion aus dem ursprünglichen Paper von Fischer und Heun verwenden.

← Nächstältere Version		Version vom 23. Dezember 2024, 22:53 Uhr
Zeile 93:		Zeile 93:
	Der interessierte Leser kann den Beweis des Lemmas in Johannes Fischer and Heun (2011, S. 472)<ref name="10.1137/090779759"/> nachlesen.		Der interessierte Leser kann den Beweis des Lemmas in Johannes Fischer and Heun (2011, S. 472)<ref name="10.1137/090779759"/> nachlesen.

	Aufgrund des Lemmas ergibt sich eine Reduktion für in-Block RMQs, da nicht jeder Block einzeln vorberechnet wird, sondern nur die Antworten für alle möglichen Kartesischen Bäume über <math>s</math> Elementen ausreichen, denn jeder Block lässt sich in Linearzeit (Johannes Fischer and Heun 2011)<ref name="10.1137/090779759"/> auf einen Kartesischen Baum abbilden, da die Baumkonstruktion amortisiert in <math>\mathcal{O}(n)</math> liegt. Die Anzahl der Bäume entspricht der Catalan-Zahl <math>\textstyle C_s = \frac{1}{s+1} \binom{2s}{s}</math>. ~~Die~~ ~~''Bitmuster''~~ ~~der~~ ~~Bäume~~ ~~dienen~~ ~~als~~ ~~''Index''~~ ~~für~~ ~~die~~ ~~vorberechnete~~ ~~in-Block~~ ~~Tabelle~~ <math>P[1,C_s][1~~,s][1,s~~]</math>. ~~Ein~~ ~~Kartesischer~~ ~~Baum~~ ~~wird~~ ~~hierbei~~ ~~durch~~ ~~seine~~ ~~''Level-order~~ ~~unary~~ ~~degree~~ ~~sequence''~~ ~~(LOUDS)~~ ~~eindeutig~~ ~~repräsentiert, welche von Jacobson (1989)<ref name="10.1109/SFCS.1989.63533">{{cite~~ ~~journal~~		Aufgrund des Lemmas ergibt sich eine Reduktion für in-Block RMQs, da nicht jeder Block einzeln vorberechnet wird, sondern nur die Antworten für alle möglichen Kartesischen Bäume über <math>s</math> Elementen ausreichen, denn jeder Block lässt sich in Linearzeit (Johannes Fischer and Heun 2011)<ref name="10.1137/090779759"/> auf einen Kartesischen Baum abbilden, da die Baumkonstruktion amortisiert in <math>\mathcal{O}(n)</math> liegt. Die Anzahl der Bäume entspricht der Catalan-Zahl <math>\textstyle C_s = \frac{1}{s+1} \binom{2s}{s}</math>, und es existiert eine Bijektion zwischen allen kartesischen Bäumen auf <math>n</math> Knoten und den Zahlen <math>[0, C_s-1]</math>, die mittels einem Algorithmus in Linearzeit berechnet werden kann<ref>{{Literatur \|Autor=Donald E. Knuth \|Titel=Generating All Trees—
			History of Combinatorial Generation \|Hrsg= \|Sammelwerk=The Art of Computer Programming \|Band=Vol. 4 \|Nummer=Fasc. 4 \|Verlag=Addison-Wesley \|Ort=Upper Saddle River, NJ \|Datum=2006 \|ISBN=9780132702348 \|Seiten=4 ff.}}</ref>. Diese numerische Repräsentation eines kartesischen Baumes wird als ''Index'' für die vorberechnete in-Block Tabelle <math>P[1,C_s][1,s][1,s]</math> verwendet, und ihr Platzbedarf kann mittels [[Stirlingformel]] als <math>\log_2 C_s \approx 2s</math> Bits abgeschätzt werden.<br />
	\| author = Jacobson, G.
	\| authorlink =
	\| year = 1989
	\| title = Space-efficient static trees and graphs
	\| journal = Foundations of Computer Science, 1989., 30th Annual Symposium
	\| pages = 549–554
	\| doi = 10.1109/SFCS.1989.63533
	}}</ref>
	beschrieben wird und <math>2n-1</math> Bits benötigt.<br />
	Insgesamt ergibt sich daraus ein Platzbedarf von <math>\|P\| = \mathcal{O}(2^{2s} \cdot s \cdot s) = \mathcal{O}(\sqrt{n}\,\log^2 n) = o(n)</math>.<br />		Insgesamt ergibt sich daraus ein Platzbedarf von <math>\|P\| = \mathcal{O}(2^{2s} \cdot s \cdot s) = \mathcal{O}(\sqrt{n}\,\log^2 n) = o(n)</math>.<br />

Aka: /* Effiziente Konstruktion */ Halbgeviertstrich

2024-05-15T06:35:11Z

Effiziente Konstruktion: Halbgeviertstrich

← Nächstältere Version		Version vom 15. Mai 2024, 08:35 Uhr
Zeile 28:		Zeile 28:
	\| title = The Cell Probe Complexity of Succinct Data Structures		\| title = The Cell Probe Complexity of Succinct Data Structures
	\| journal = Automata, Languages and Programming		\| journal = Automata, Languages and Programming
	\| pages = ~~190-190~~		\| pages = 190–190
	\| doi = 10.1007/3-540-45061-0_28		\| doi = 10.1007/3-540-45061-0_28
	\| pmid =		\| pmid =

Thomas Dresler: Tippfehler korrigiert

2024-05-14T20:27:14Z

Tippfehler korrigiert

← Nächstältere Version		Version vom 14. Mai 2024, 22:27 Uhr
Zeile 17:		Zeile 17:

	* '''Lineares Scannen:''' Durch ''Scannen'' von <math>A[l, r]</math> wird für jede Query eine ''lineare'' Anfragezeit in <math>\mathcal{O}(n)</math> worst-case und ein Platzbedarf von <math>\mathcal{O}(n)</math> erreicht.		* '''Lineares Scannen:''' Durch ''Scannen'' von <math>A[l, r]</math> wird für jede Query eine ''lineare'' Anfragezeit in <math>\mathcal{O}(n)</math> worst-case und ein Platzbedarf von <math>\mathcal{O}(n)</math> erreicht.
	* '''Vorberechnung einer Lookup Tabelle:''' Naiv wird eine Tabelle vorberechnet, die die Antworten auf alle möglichen Range Minimum Anfragen speichert. Somit wird eine ''konstante'' Anfragezeit in <math>\mathcal{O}(1)</math> erreicht, wobei <math>\tbinom{n}{2}</math> Kombinationen <math>\mathcal{O}(n^2)</math> Platz benötigen.		* '''Vorberechnung einer Lookup-Tabelle:''' Naiv wird eine Tabelle vorberechnet, die die Antworten auf alle möglichen Range Minimum Anfragen speichert. Somit wird eine ''konstante'' Anfragezeit in <math>\mathcal{O}(1)</math> erreicht, wobei <math>\tbinom{n}{2}</math> Kombinationen <math>\mathcal{O}(n^2)</math> Platz benötigen.

	Angenommen wird allerdings, dass es sich bei <math>A</math> um ein statisches Array handelt und die Anfragen on-line gestellt werden, wodurch eine geschickte Vorberechnung und die Konstruktion einer geeigneten Datenstruktur die Anfragezeit deutlich reduzieren kann. Hierbei wird eine nahezu ''konstante'' Anfragezeit mit ''linearem'' Platzverbrauch angestrebt.		Angenommen wird allerdings, dass es sich bei <math>A</math> um ein statisches Array handelt und die Anfragen on-line gestellt werden, wodurch eine geschickte Vorberechnung und die Konstruktion einer geeigneten Datenstruktur die Anfragezeit deutlich reduzieren kann. Hierbei wird eine nahezu ''konstante'' Anfragezeit mit ''linearem'' Platzverbrauch angestrebt.

Aka: /* Einzelnachweise */ bereits in Unterkategorie enthalten

2023-03-22T21:29:48Z

Einzelnachweise: bereits in Unterkategorie enthalten

← Nächstältere Version		Version vom 22. März 2023, 23:29 Uhr
Zeile 155:		Zeile 155:

	[[Kategorie:Suchalgorithmus]]		[[Kategorie:Suchalgorithmus]]
	[[Kategorie:Algorithmus]]

Rolf acker: /* Effiziente Konstruktion */ typo ("[S]truktur")

2021-04-05T11:43:13Z

Effiziente Konstruktion: typo ("[S]truktur")

← Nächstältere Version		Version vom 5. April 2021, 13:43 Uhr
Zeile 22:		Zeile 22:

	== Effiziente Konstruktion ==		== Effiziente Konstruktion ==
	Die vorberechneten RMQ-~~Datenstukturen~~ können in zwei Kategorien eingeteilt werden: (a) Array-Indexierung und (b) Array-Codierung. Im Fall (a) benötigt die vorberechnete Struktur Zugriff auf das Array <math>A</math> um darauf RMQs zu beantworten. Im Fall (b) ist ein Zugriff auf <math>A</math> nicht notwendig, um eine RMQ zu beantworten.<ref name="10.1007/3-540-45061-0_28">{{cite journal		Die vorberechneten RMQ-Datenstrukturen können in zwei Kategorien eingeteilt werden: (a) Array-Indexierung und (b) Array-Codierung. Im Fall (a) benötigt die vorberechnete Struktur Zugriff auf das Array <math>A</math> um darauf RMQs zu beantworten. Im Fall (b) ist ein Zugriff auf <math>A</math> nicht notwendig, um eine RMQ zu beantworten.<ref name="10.1007/3-540-45061-0_28">{{cite journal
	\| author = Gál, A. and Miltersen, P.		\| author = Gál, A. and Miltersen, P.
	\| authorlink =		\| authorlink =
Zeile 91:		Zeile 91:

	'''Lemma: ''' Falls die Kartesischen Bäume zweier Arrays <math>B_i, B_j; i\ne j</math> die gleiche Struktur aufweisen, so gilt <math>\forall l,r; 1 \le l \le r \le n : \operatorname{RMQ}_{B_i}(l, r) = \operatorname{RMQ}_{B_j}(l, r)</math>.<br />		'''Lemma: ''' Falls die Kartesischen Bäume zweier Arrays <math>B_i, B_j; i\ne j</math> die gleiche Struktur aufweisen, so gilt <math>\forall l,r; 1 \le l \le r \le n : \operatorname{RMQ}_{B_i}(l, r) = \operatorname{RMQ}_{B_j}(l, r)</math>.<br />
	Der interessierte Leser kann den Beweis des Lemmas in Johannes Fischer and Heun (2011, S.472)<ref name="10.1137/090779759"/> nachlesen.		Der interessierte Leser kann den Beweis des Lemmas in Johannes Fischer and Heun (2011, S. 472)<ref name="10.1137/090779759"/> nachlesen.

	Aufgrund des Lemmas ergibt sich eine Reduktion für in-Block RMQs, da nicht jeder Block einzeln vorberechnet wird, sondern nur die Antworten für alle möglichen Kartesischen Bäume über <math>s</math> Elementen ausreichen, denn jeder Block lässt sich in Linearzeit (Johannes Fischer and Heun 2011)<ref name="10.1137/090779759"/> auf einen Kartesischen Baum abbilden, da die Baumkonstruktion amortisiert in <math>\mathcal{O}(n)</math> liegt. Die Anzahl der Bäume entspricht der Catalan-Zahl <math>\textstyle C_s = \frac{1}{s+1} \binom{2s}{s}</math>. Die ''Bitmuster'' der Bäume dienen als ''Index'' für die vorberechnete in-Block Tabelle <math>P[1,C_s][1,s][1,s]</math>. Ein Kartesischer Baum wird hierbei durch seine ''Level-order unary degree sequence'' (LOUDS) eindeutig repräsentiert, welche von Jacobson (1989)<ref name="10.1109/SFCS.1989.63533">{{cite journal		Aufgrund des Lemmas ergibt sich eine Reduktion für in-Block RMQs, da nicht jeder Block einzeln vorberechnet wird, sondern nur die Antworten für alle möglichen Kartesischen Bäume über <math>s</math> Elementen ausreichen, denn jeder Block lässt sich in Linearzeit (Johannes Fischer and Heun 2011)<ref name="10.1137/090779759"/> auf einen Kartesischen Baum abbilden, da die Baumkonstruktion amortisiert in <math>\mathcal{O}(n)</math> liegt. Die Anzahl der Bäume entspricht der Catalan-Zahl <math>\textstyle C_s = \frac{1}{s+1} \binom{2s}{s}</math>. Die ''Bitmuster'' der Bäume dienen als ''Index'' für die vorberechnete in-Block Tabelle <math>P[1,C_s][1,s][1,s]</math>. Ein Kartesischer Baum wird hierbei durch seine ''Level-order unary degree sequence'' (LOUDS) eindeutig repräsentiert, welche von Jacobson (1989)<ref name="10.1109/SFCS.1989.63533">{{cite journal

Aka: /* Linearithmischer Platzbedarf */ https

2021-02-16T19:52:30Z

Linearithmischer Platzbedarf: https

← Nächstältere Version		Version vom 16. Februar 2021, 21:52 Uhr
Zeile 52:		Zeile 52:
	\| pmid =		\| pmid =
	\| id = {{ISSN\|01966774}}		\| id = {{ISSN\|01966774}}
	\| url = ~~http~~://linkinghub.elsevier.com/retrieve/pii/S0196677405000854		\| url = https://linkinghub.elsevier.com/retrieve/pii/S0196677405000854
	}}</ref> wird eine Möglichkeit beschrieben, um <math>\langle\mathcal{O}(n \log n), \mathcal{O}(1)\rangle</math> zu erreichen. Hierzu werden die Ergebnisse für alle möglichen Startpositionen <math>(1, \dots, n)</math> und Längen der Form <math>2^i : i \leq x=\mathcal{O}(\log n)</math> vorberechnet. Aufgrund dessen wird die tatsächliche RMQ in maximal zwei gleich lange Teilanfragen zerlegt, deren Längen Zweierpotenzen sind und sich möglicherweise überlappen. Hierbei wird die größtmögliche Zweierpotenz <math>h</math> gewählt, wobei <math>h = \lfloor \log_2{(r-l+1)} \rfloor</math> ist. Aufgrund der Vorberechnung kann das Ergebnis über das Intervall von <math>2^h</math> in konstanter Zeit bestimmt werden. Abbildung 2 verbildlicht das Vorgehen und zeigt beispielhaft, wie die RMQ (Intervall = rote Linie) in zwei RMQs (graue Linien) zerlegt wird.<br />		}}</ref> wird eine Möglichkeit beschrieben, um <math>\langle\mathcal{O}(n \log n), \mathcal{O}(1)\rangle</math> zu erreichen. Hierzu werden die Ergebnisse für alle möglichen Startpositionen <math>(1, \dots, n)</math> und Längen der Form <math>2^i : i \leq x=\mathcal{O}(\log n)</math> vorberechnet. Aufgrund dessen wird die tatsächliche RMQ in maximal zwei gleich lange Teilanfragen zerlegt, deren Längen Zweierpotenzen sind und sich möglicherweise überlappen. Hierbei wird die größtmögliche Zweierpotenz <math>h</math> gewählt, wobei <math>h = \lfloor \log_2{(r-l+1)} \rfloor</math> ist. Aufgrund der Vorberechnung kann das Ergebnis über das Intervall von <math>2^h</math> in konstanter Zeit bestimmt werden. Abbildung 2 verbildlicht das Vorgehen und zeigt beispielhaft, wie die RMQ (Intervall = rote Linie) in zwei RMQs (graue Linien) zerlegt wird.<br />
	Sei <math>M</math> die Tabelle mit den vorberechneten Antworten. Der Algorithmus umfasst insgesamt drei Schritte, um das Ergebnis einer RMQ zu bestimmen:		Sei <math>M</math> die Tabelle mit den vorberechneten Antworten. Der Algorithmus umfasst insgesamt drei Schritte, um das Ergebnis einer RMQ zu bestimmen:

← Nächstältere Version		Version vom 23. Dezember 2024, 23:32 Uhr
Zeile 94:		Zeile 94:

	Aufgrund des Lemmas ergibt sich eine Reduktion für in-Block RMQs, da nicht jeder Block einzeln vorberechnet wird, sondern nur die Antworten für alle möglichen Kartesischen Bäume über <math>s</math> Elementen ausreichen, denn jeder Block lässt sich in Linearzeit (Johannes Fischer and Heun 2011)<ref name="10.1137/090779759"/> auf einen Kartesischen Baum abbilden, da die Baumkonstruktion amortisiert in <math>\mathcal{O}(n)</math> liegt. Die Anzahl der Bäume entspricht der Catalan-Zahl <math>\textstyle C_s = \frac{1}{s+1} \binom{2s}{s}</math>, und es existiert eine Bijektion zwischen allen kartesischen Bäumen auf <math>s</math> Knoten und den Zahlen <math>[1, C_s]</math>, die mittels einem Algorithmus in Linearzeit berechnet werden kann<ref>{{Literatur \|Autor=Donald E. Knuth \|Titel=Generating All Trees—		Aufgrund des Lemmas ergibt sich eine Reduktion für in-Block RMQs, da nicht jeder Block einzeln vorberechnet wird, sondern nur die Antworten für alle möglichen Kartesischen Bäume über <math>s</math> Elementen ausreichen, denn jeder Block lässt sich in Linearzeit (Johannes Fischer and Heun 2011)<ref name="10.1137/090779759"/> auf einen Kartesischen Baum abbilden, da die Baumkonstruktion amortisiert in <math>\mathcal{O}(n)</math> liegt. Die Anzahl der Bäume entspricht der Catalan-Zahl <math>\textstyle C_s = \frac{1}{s+1} \binom{2s}{s}</math>, und es existiert eine Bijektion zwischen allen kartesischen Bäumen auf <math>s</math> Knoten und den Zahlen <math>[1, C_s]</math>, die mittels einem Algorithmus in Linearzeit berechnet werden kann<ref>{{Literatur \|Autor=Donald E. Knuth \|Titel=Generating All Trees—
	History of Combinatorial Generation \|Hrsg= \|Sammelwerk=The Art of Computer Programming \|Band=Vol. 4 \|Nummer=Fasc. 4 \|Verlag=Addison-Wesley \|Ort=Upper Saddle River, NJ \|Datum=2006 \|ISBN=~~9780132702348~~ \|Seiten=4 ff.}}</ref>. Diese numerische Repräsentation eines kartesischen Baumes wird als ''Index'' für die vorberechnete in-Block Tabelle <math>P[1,C_s][1,s][1,s]</math> verwendet, und ihr Platzbedarf kann mittels [[Stirlingformel]] als <math>\log_2 C_s \approx 2s</math> Bits abgeschätzt werden.<br />		History of Combinatorial Generation \|Hrsg= \|Sammelwerk=The Art of Computer Programming \|Band=Vol. 4 \|Nummer=Fasc. 4 \|Verlag=Addison-Wesley \|Ort=Upper Saddle River, NJ \|Datum=2006 \|ISBN=9780321335708 \|Seiten=4 ff.}}</ref>. Diese numerische Repräsentation eines kartesischen Baumes wird als ''Index'' für die vorberechnete in-Block Tabelle <math>P[1,C_s][1,s][1,s]</math> verwendet, und ihr Platzbedarf kann mittels [[Stirlingformel]] als <math>\log_2 C_s \approx 2s</math> Bits abgeschätzt werden.<br />
	Insgesamt ergibt sich daraus ein Platzbedarf von <math>\|P\| = \mathcal{O}(2^{2s} \cdot s \cdot s) = \mathcal{O}(\sqrt{n}\,\log^2 n) = o(n)</math>.<br />		Insgesamt ergibt sich daraus ein Platzbedarf von <math>\|P\| = \mathcal{O}(2^{2s} \cdot s \cdot s) = \mathcal{O}(\sqrt{n}\,\log^2 n) = o(n)</math>.<br />