定義

セグメントツリーは配列を「区間(segment)」に分割し、各区間の合をノードに保存した二分木です。ルートは全区間、葉は要素1個を担当します。

主な特性

• ✓各ノード = 区間[l, r]の合。親の合 = 2つの子の合。
• ✓クエリ: 区間を完全に覆うノードを数個選んで合わせるのでO(log n)。
• ✓点更新: 葉からルートまでの1経路のノードだけ再合算するのでO(log n)。

時間計算量