Preuve de complexité temporelle pour la mise en œuvre de l'arborescence des segments du problème de somme à distance

Je comprends que les arbres du segment peuvent être utilisés pour trouver la somme de tableau sous de . Et que cela peut se faire en temps selon le tutoriel ici .O ( log n $A$$\mathcal{O}(\log n)$

Cependant, je ne suis pas en mesure de prouver que le temps d'interrogation est bien . Ce lien (et bien d'autres) dit que nous pouvons prouver qu'à chaque niveau, le nombre maximum de nœuds traités est de et donc .4 O ( 4 log n ) = O ( log n $\mathcal{O}(\log n)$$4$$\mathcal{O}(4 \log n) = \mathcal{O}(\log n)$

Mais comment le prouver, peut-être par contradiction?

Et si oui, si nous devions utiliser des arbres de segments pour la somme à distance de tableaux de dimensions supérieures, comment la preuve serait-elle étendue?

Par exemple, je peux penser à trouver une somme de sous-matrice en divisant la matrice d'origine en 4 quadrants (similaire aux intervalles de moitié dans les tableaux linéaires) en construisant un arbre de segment de quadrant mais la preuve m'échappe.

L'affirmation est qu'il existe au plus nœuds qui sont étendus à chaque niveau. Nous le prouverons par contradiction.$2$

Considérez l'arborescence des segments ci-dessous.

Disons qu'il y a nœuds qui sont développés dans cet arbre. Cela signifie que la plage va du nœud le plus à gauche au nœud le plus à droite. Mais notez que si la plage s'étend jusqu'au nœud le plus à droite, alors la plage complète du nœud central est couverte. Ainsi, ce nœud renverra immédiatement la valeur et ne sera pas développé. Ainsi, nous prouvons qu'à chaque niveau, nous développons au plus nœuds et puisqu'il existe des niveaux , les nœuds qui sont développés sont2 log n 2 ⋅ log n = Θ ( log n$3$$2$$\log{n}$$\boxed{2 \cdot \log{n} = \Theta\left( {\log{n}} \right)}$