Prova de complexidade de tempo para a implementação da árvore de segmentos do problema de soma à distância

10

Eu entendo que as árvores segmento pode ser usado para encontrar a soma de sub variedade de . E isso pode ser feito no tempo O ( log n ) de acordo com o tutorial aqui .UMAO(registron)

No entanto, não sou capaz de provar que o tempo de consulta é realmente . Esse link (e muitos outros) diz que podemos provar que, em cada nível, o número máximo de nós processados ​​é 4 e, portanto, O ( 4 log n ) = O ( log n ) .O(registron)4O(4registron)=O(registron)

Mas como provamos isso, talvez por contradição?

E se sim, se usássemos árvores de segmentos para soma variada de matrizes dimensionais mais altas, como a prova seria estendida?

Por exemplo, eu posso pensar em encontrar uma soma sub-matriz dividindo a matriz original em 4 quadrantes (semelhante a intervalos de metade em matrizes lineares) construindo uma árvore de segmentos de quadrante, mas a prova me escapa.

Arijit Choudhury
fonte
a construção da árvore de segmentos é O (n), a consulta é O (log n) e a atualização é O (log N). Seu benefício sobre a matriz de soma está na complexidade da atualização.
19417

Respostas:

11

A alegação é que existem no máximo nós que são expandidos em cada nível. Vamos provar isso por contradição.2

Considere a árvore de segmentos fornecida abaixo.

Árvore de segmentos

32registron2registron=Θ(registron)

adijo
fonte