Optymalne przetwarzanie wstępne dla niektórych rodzajów zapytań

Załóżmy, że mamy półgrupę z elementami . Naszym celem jest obliczanie produktów .$(S,\circ)$$S=\lbrace s_1,s_2,\dots,s_n\rbrace$$s_i\circ s_{i+1}\circ \cdots\circ s_j$

W swoim artykule „Optymalne przetwarzanie wstępne dla odpowiedzi na zapytania produktów on-line” Alon i Schieber udowadniają, że możemy odpowiedzieć na każde takie zapytanie w co najwyżej krokach (gdzie jest odwrotną funkcją Ackermanna), używając tylko liniowa ilość przetwarzania wstępnego.$O(\alpha(n))$$\alpha$

Jeśli pożądane jest, aby na każde zapytanie można było odpowiedzieć w krokach , czy można to zrobić tylko przy użyciu liniowego przetwarzania wstępnego?$s_i\circ s_{i+1}\circ \cdots\circ s_j$$O(\log(j-i))$

(To pytanie jest inspirowana przez tego ostatniego pytania przez Brendan McKay na Mathoverflow).

Skonstruuj uporządkowane zrównoważone drzewo binarne za pomocą w liściach (w kolejności). W każdym wewnętrznym węźle przechowuj iloczyn liści poddrzewa zrootowanych na . Ten przerób oczywiście prowadzi w O czasie i przestrzeni.$s_1,\dots,s_n$$v$$v$$(n)$

Teraz, aby obliczyć produkt (gdzie ) przejdź do drzewa od do najmniejszego wspólnego przodka (LCA) i . Zbierz produkty przechowywane w każdym prawym dziecku zwisającym ze ścieżki, z wyłączeniem odpowiedniego dziecka LCA. Innymi słowy, gdy przechodzisz od do jego rodzica , jeśli jest lewym dzieckiem , to podnieś produkt przechowywany w prawym dziecku . Podobnie, przejdź od do LCA i zbierz produkty przechowywane u pozostawionych dzieci zwisających z tej ścieżki. Pomnóż wszystkie te produkty wraz z i$s_i\circ\ldots\circ s_j$$i<j$$i$$i$$j$$u$$v$$u$$v$$v$$j$$s_i$$s_j$ w kolejności.