セグメント ツリーを使用して、A のサブ配列の合計を見つけることができることを理解しています。また、こちらのチュートリアルに従って、O(logn) 時間で実行できることも理解しています。
ただし、クエリ時間が実際に O(logn) であることを証明することはできません。このリンク (および他の多くのリンク) は、各レベルで処理されるノードの最大数が 4 であることを証明できるため、O(4logn) == O(logn) であると述べています。しかし、おそらく矛盾によって、これをどのように証明するのでしょうか?
もしそうなら、より高次元の配列の範囲和にセグメント ツリーを使用するとしたら、証明はどのように拡張されるでしょうか?
たとえば、元の行列を 4 つの象限 (線形配列で間隔を半分にするのと同様) に分割して、象限セグメント ツリーを構築することで部分行列の合計を見つけることを考えることができますが、証明はわかりません。