Preprocesamiento óptimo para ciertos tipos de consultas

Supongamos que tenemos un semigrupo con elementos S = { s 1 , s 2 , ... , s n } . Nuestro objetivo es calcular productos 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$

En su artículo "Preprocesamiento óptimo para responder consultas de productos en línea", Alon y Schieber demuestran que podemos responder a cada una de esas consultas en la mayoría de los pasos (donde α es la función inversa de Ackermann) usando solo una cantidad lineal de preprocesamiento.$O(\alpha(n))$$\alpha$

Si se desea que cada consulta pueda responderse en pasos O ( log ( j - i ) ) , ¿se puede hacer esto solo con un preprocesamiento lineal?$s_i\circ s_{i+1}\circ \cdots\circ s_j$$O(\log(j-i))$

(Esta pregunta está inspirada en esta pregunta reciente de Brendan McKay en Mathoverflow).

$s_1,\dots,s_n$$v$$v$$(n)$

$s_i\circ\ldots\circ s_j$$i<j$$i$$i$$j$$u$$v$$u$$v$$v$$j$$s_i$$s_j$