Оптимальная предварительная обработка для определенных типов запросов

Предположим, у нас есть полугруппа с элементами . Наша цель - вычислить произведения .S = { s 1 , s 2 , … , s n } s i ∘ s i + 1 ∘ ⋯ ∘ s $(S,\circ)$$S=\lbrace s_1,s_2,\dots,s_n\rbrace$$s_i\circ s_{i+1}\circ \cdots\circ s_j$

В своей статье «Оптимальная предварительная обработка для ответа на онлайн-запросы продукта» Алон и Шибер доказывают, что мы можем ответить на каждый такой запрос не более чем за шагов (где - обратная функция Аккермана), используя только линейная величина предварительной обработки.$O(\alpha(n))$$\alpha$

Если желательно, чтобы на каждый запрос можно было ответить с помощью шагов , можно ли делать это только с помощью линейной предварительной обработки? O ( журнал ( J - я ) $s_i\circ s_{i+1}\circ \cdots\circ s_j$$O(\log(j-i))$

(Этот вопрос навеян этим недавний вопрос Брендан Маккей в Mathoverflow.)

Построить упорядоченное сбалансированное двоичное дерево с в листьях (по порядку). В каждом внутреннем узле хранится произведение листьев поддерева с корнем в . Эта предварительная обработка, очевидно, выполняется в O времени и пространстве. v v ( n $s_1,\dots,s_n$$v$$v$$(n)$

Теперь, чтобы вычислить произведение (где ), поднимите дерево от до наименее общего предка (LCA) из и . Соберите продукты, хранящиеся у каждого правого ребенка, свисающего с пути, за исключением правого ребенка LCA. Другими словами, когда вы переходите от к его родительскому , если - левый дочерний элемент , тогда выберите продукт, хранящийся в правом дочернем . Аналогичным образом, подойдите от к LCA и соберите продукты, хранящиеся у оставленных детей, свисающих с этого пути. Умножьте все эти продукты вместе с и я < J я я J у v U v v J S I сек $s_i\circ\ldots\circ s_j$$i<j$$i$$i$$j$$u$$v$$u$$v$$v$$j$$s_i$$s_j$ в порядке.