Pré-processamento ideal para certos tipos de consultas

11

Suponha que tenhamos um semigrupo com os elementos S = { s 1 , s 2 , , s n } . Nosso objetivo é produtos de computação s is i + 1s j .(S,)S={s1,s2,,sn}sisi+1sj

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.O(α(n))α

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?sisi+1sjO(log(ji))

(Esta pergunta é inspirada nesta pergunta recente de Brendan McKay no Mathoverflow.)

Gjergji Zaimi
fonte
1
você pode adicionar um link para a pergunta do MO?
Suresh Venkat
1
Alguma razão para ser um semigrupo e não um grupo?
Huck Bennett
1
@ Huck: Se for um grupo, a construção de Noam no link acima fornece esse algoritmo.
Gjergji Zaimi 09/09/11

Respostas:

2

s1,,snvv(n)

sisji<jiijuvuvvjsisj

Ari
fonte