Optimale Vorverarbeitung für bestimmte Arten von Abfragen

Angenommen, wir haben eine Halbgruppe mit Elementen S = { s 1 , s 2 , … , s n } . Unser Ziel ist es , rechen Produkte s i ∘ s i + 1 ∘ ⋯ ∘ s j .$(S,\circ)$$S=\lbrace s_1,s_2,\dots,s_n\rbrace$$s_i\circ s_{i+1}\circ \cdots\circ s_j$

In ihrer Arbeit "Optimale Vorverarbeitung für die Beantwortung von Online-Produktanfragen" beweisen Alon und Schieber, dass wir jede solche Anfrage in höchstens Schritten (wobei α die inverse Ackermann-Funktion ist) nur unter Verwendung eines linearen Betrags beantworten können der Vorverarbeitung.$O(\alpha(n))$$\alpha$

Wenn es gewünscht wird, dass jede Abfrage kann beantwortet werden , O ( log ( j - i ) ) Schritte, kann man immer noch diese lineare Vorverarbeitung mit nur tun?$s_i\circ s_{i+1}\circ \cdots\circ s_j$$O(\log(j-i))$

(Diese Frage wird von inspiriert dieser letzten Frage von Brendan McKay bei Mathoverflow.)

Konstruieren Sie einen geordneten ausgeglichenen Binärbaum mit in den Blättern (in der Reihenfolge). In jedem internen Knoten v wird das Produkt der Blätter des Teilbaums gespeichert, der bei v verwurzelt ist . Diese Vorverarbeitung läuft offensichtlich in O ( n ) Zeit und Raum ab.$s_1,\dots,s_n$$v$$v$$(n)$

Um nun ein Produkt zu berechnen (wobei i < j ), gehen Sie den Baum von i zum am wenigsten verbreiteten Vorfahren (LCA) von$s_i\circ\ldots\circ s_j$$i<j$$i$$i$$j$$u$$v$$u$$v$$v$$j$$s_i$$s_j$