67. C# による遅延評価セグメント木の抽象化実装

競技プログラミングでよく使われる「セグメント木」というデータ構造があります。

これは、配列データに対して2のべき乗区間ごとに「合計値」「最大値」など注目したい演算を適用しておき、任意の区間に対する演算結果を $O(\log n)$ で取得できるものです。

f:id:ibako_piyo:20220215201226p:plain — セグメント木のイメージ

例えば、上記セグメント木は黄色で示した配列（8要素）が実データです。それに対して、注目している演算は「合計値」です。

セグメント木は区間に対する問い合わせ(Query)を $O(\log n)$ で実現できて、要素に対する更新(Update)を $O(\log n)$ で実現できます。そのため、区間に対する更新(Update)は $O(n\log n)$ の計算量を要します。

しかし、よく考えると区間に対する更新は無駄な計算が多いことが分かります。
例えば、全要素を更新することを考えます。愚直に実装すると、1要素の更新ごとに先祖区間を全て更新します。ところが、次の要素を更新する際も先ほど更新した先祖区間を更新することになります。このように何度も同じ区間を見ることになり、無駄が多いです。

ここから、区間更新の計算量を $O(\log n)$ に落とすため「遅延評価セグメント木」というものを考えます。

遅延評価とは一般的な計算機科学用語で、「必要になるまで値の計算（＝評価）を遅らせる」評価戦略を表します。セグメント木でいうと、あるセグメントに対する問い合わせ(Query)が発生するまで、そのセグメントに対する評価を遅らせることを目指します。

遅延評価セグメント木では、セグメント実データ値の他に遅延評価値を保持します。

例えば、先ほどの図の例で「index: 0～5 の要素に 10 を加算する」という操作を遅延評価セグメント木で行う場合、以下の図のようなイメージになります。赤文字が遅延評価値で、緑のセグメントが遅延評価値を保持しています。

f:id:ibako_piyo:20220215204216p:plain — 遅延評価セグメント木（イメージ）

ただ、実際の実装では先祖セグメントは正しいデータを保持していないと（後の問い合わせで）困るという事情があるため、注目しているセグメントまでは評価を行い、その下のセグメントに遅延評価値を伝播させておきます。つまり、注目しているセグメントより下のセグメントは評価を行わない（遅延させる）ということです。

f:id:ibako_piyo:20220215204502p:plain — index: 0~5 更新後の実際の状態

（ここから内容がやや難しいです）

通常のセグメント木は、「2つの子セグメントから親セグメントへの演算」を適用して構築されます。ところが、遅延評価セグメント木は性質上、「既存のセグメント値と遅延評価値からセグメント値を更新する」ことができる必要があります。よって、適用する更新演算を予め与えておく必要があります。また、更新演算が「加算」であればセグメントの包括する要素数によって加算値が変化するため、「セグメント長」も変数になる場合があります。

調べたところ、通常のセグメント木とは異なり遅延評価セグメント木は実装の幅がかなり広い印象です。特に高度な抽象化を目指す場合、何を変数とするかが人によって結構違います。私は Update / Query に対して「加算」「最大値」の2パターンが存在すると考えて、この組み合わせである4通りに対して抽象化を行いました。その結果、以下のような演算と元を定義する必要がありました。ここで、 $D$ は実データ値となる元の集合、 $L$ は遅延評価値となる元の集合です。

- 2つの子セグメントの実データ値から、実データ値への演算
- 親子セグメント、合計3セグメントに注目した演算です
- 既存のセグメントデータ値と遅延評価値から、実データ値への演算
- 1セグメントに注目した演算です
- 葉（＝配列要素）について、既存のセグメントデータ値と遅延評価値から、実データ値への演算
- 1セグメントに注目した演算です
- 既存の遅延評価値と指定する遅延評価値から、更新後の遅延評価値への演算
- 1セグメントに注目した演算です
- 遅延評価値とセグメント長から、指定する遅延評価値への演算
- $\mathbb{N}$ は自然数全体の集合で、C# でいうと int や long と考えると良いです
- 1セグメントに注目した演算です
- 実データ値の単位元
- $\forall x \in D$ について $F(x, e_D) = F(e_D, x) = x$ となるような値です。例えば、演算が「加算」であれば $0$ 、「最小値」であれば $\infty$ になります。
- 遅延評価値の単位元
- $\forall x \in L$ について $H(x, e_L) = H(e_L, x) = x$ となるような値です