要素の更新と区間和
配列=\lbrace 1,3,5,7,9,11,13,15\rbrace がある。\\
\begin{align}
& Q, この配列の第 2 項から第 7 項までの和を求めよ。 \\
& Q, この配列の第 2 項に 1 を足せ。 \\
& Q, この配列の第 2 項から第 7 項までの和を求めよ。 \\
\end{align}
上のような計算処理を行いたい場合、様々なデータ構造が考えられます。$n$ が小さい場合は何を使ってもよいと思いますが、大きい場合は計算のオーダーが変わってきますので、競技プログラミングや大規模データ処理の場合は最適な選択が求められます。
ナイーブな配列
まずは一番シンプルな方法から。素の配列で計算をします。処理の過程は以下のようになります。
要素の変更はすぐできますが、区間和を求める場合にはその長さだけ計算が必要になります。何回も区間和を求める必要がある場合には非効率になります。
累積和
そこで、事前に累積和を求めておいて、区間和を一瞬で求められるようにするという工夫が考えられます。累積和についての説明は累積和を何も考えずに書けるようにする！が詳しいです。
このような配列を事前に計算しておけば、各区間和は一瞬で求められます。
しかしこれも万能ではなく、実は要素を変更する度にその都度全要素を更新しなければならないというデメリットがあります。
一回計算してしまえば、区間和は一瞬で計算できるようになるので、更新をせずに区間和を求め続けるだけ、という場合はこれが最適になります。
フェニック木（BIT）
ここからややテクニカルな話になります。更新を続けるだけならナイーブな配列が有利、区間和を求め続けるなら累積和が有利、ならば更新も区間和計算も入り交じるような場合にはどうすればよいでしょうか。
実は、両方の処理に特化はしてないが両者ともそれなりにできるという赤魔道士みたいなデータ構造が存在します。それがフェニック木（Binary Indexed Tree, BIT）です。フェニック木（BIT）についての説明はBinary Indexed Tree (BIT) 総まとめ！区間加算や二次元BITまでが詳しいです。
それがこのようなものです。上の図だけ見るとわかりづらいですが、各項は元の配列のある部分の区間和になっています。（次節のセグメント木の図を見比べたらわかりやすいかもです）
- 1 = 1
- 4 = 1 + 3
- 5 = 5
- 16 = 1 + 3 + 5 + 7
...
これにより、要素の更新も区間和の計算も「少しの計算」で行えます。具体的な処理の様子は以下になります。
セグメント木
ちなみに区間和だけなら上のフェニック木で対応できますが、「任意の区間の最小値」といったような操作には使えません。より操作を拡張したデータ構造にセグメント木があります。超赤魔道士ですね。次セクションの説明に使うので、せっかくなのでここでも説明しておきます。セグメント木の説明はセグメント木を徹底解説！0から遅延評価やモノイドまでが詳しいです。
元の配列をセグメント木にすると以下のようになります。
区間を二倍しながら足して完全二分木にしていきます。先に述べたフェニック木よりもこちらの方が、元の配列をどのように加工しているかわかりやすいかもしれません。
具体的な処理の様子は以下になります。
区間加算
配列=\lbrace 1,3,5,7,9,11,13,15\rbrace がある。\\
\begin{align}
& Q, この配列の第 2 項から第 7 項までに 1 を足せ。 \\
& Q, この配列の第 1 項から第 4 項までに 2 を足せ。 \\
& Q, この配列の第 2 項から第 7 項までの和を求めよ。 \\
\end{align}
今度は、上のような計算処理を考えます。
ナイーブな配列
まずは一番シンプルな方法から。
ある区間のすべての要素に逐次的な操作を行うと時間がかかります。これを効率化した方法が、いもす法と呼ばれるものです。
いもす法
これは、区間加算を考える時に、区間のはじめに足す数、区間の終わり（直後）にそれを打ち消す数を起くことによって、後で累積和を計算する時にまとめて区間加算を扱えるというものです。言葉にするとわかりづらいので、以下の図を見た方がわかりやすいと思います。
これにより、区間加算をする時にいちいち逐次計算をせずに、最後に1回の「精算」で済むというメリットがあります。しかしこれにも弱点はあり、精算をする前では要素が確定しません。区間加算と区間和の計算が入り交じるような時には何回も精算が必要になります。
区間加算と区間和の計算をバランスよくできるような何かはないものか……。
遅延評価セグメント木
それを可能にしたのが、前節で出てきたセグメント木を強化した遅延評価セグメント木になります。セグメント木の時点で超赤魔道士なのに、それを更に強化してしまいました（実装も大変です）。
遅延評価セグメント木に区間加算をした時は、以下のようになります。
図も一気に複雑になりました。まず、セグメント木の各部分に対して、最適な二分木セグメントに対して区間和を与えます。
これはそのまま加算するのではなく、遅延値（水色）として与えられます。元のセグメント木の配列のデータは変えません。しかし、いつかは反映しなければならないので、今必要なオーダーのギリギリ上流まで反映（評価）させます。
この時、評価に必要なオーダーよりも細かい下流まで無理に見ないことが重要で、これによって逐次的な計算をせずに区間加算ができます。
キリの良い区間を区間加算すると、よりわかりやすいです。
区間和を計算する時は、必要な部分は評価が反映されることにより、正しい区間和が計算できます。
まとめ
以下の表では、平易な説明のために口語的に表現していた部分を以下のように置き換えています。
-「すぐにできる」: $O(1)$
-「少し時間がかかる」: $O(\log n)$
-「すごく時間がかかる」: $O(n)$
$O$記法についてはオーダー記法の定義と大雑把な意味を参考まで。
要素の変更と区間和
| 方法 | 要素の変更 | 区間和の計算 |
|---|---|---|
| ナイーブ計算 | $O(1)$ | $O(n)$ |
| 累積和 | $O(n)$ | $O(1)$ |
| フェニック木 | $O(\log n)$ | $O(\log n)$ |
| セグメント木 | $O(\log n)$ | $O(\log n)$ |
区間加算と区間和
| 方法 | 区間加算 | 区間和の計算 |
|---|---|---|
| ナイーブ計算 | $O(n)$ | $O(n)$ |
| いもす法 | $O(1)$※ | $O(n)$ |
| 遅延評価セグメント木 | $O(\log n)$ | $O(\log n)$ |
※区間和の計算の前に $O(n)$の精算が必要