Suponha que tenhamos um semigrupo com os elementos S = { s 1 , s 2 , … , s n } . Nosso objetivo é produtos de computação s i ∘ s i + 1 ∘ ⋯ ∘ s j .
Em seu artigo "Pré-processamento ideal para responder a consultas de produtos on-line", Alon e Schieber provam que podemos responder cada uma dessas consultas em no máximo etapas (onde α é a função inversa de Ackermann) usando apenas uma quantidade linear de pré-processamento.
Se for desejado que cada consulta podem ser respondidas em O ( log ( j - i ) ) passos, pode-se ainda fazer isto com apenas linear pré-processamento?
(Esta pergunta é inspirada nesta pergunta recente de Brendan McKay no Mathoverflow.)
cc.complexity-theory
graph-theory
ds.data-structures
Gjergji Zaimi
fonte
fonte
Respostas:
fonte