セグメント木の理屈を学ぶ(3) 遅延セグメント木のデータ構造

「セグメント木の理屈を学ぶ(1) データ構造とモノイド構造の整合性」「セグメント木の理屈を学ぶ(2) 不変条件を同型として読み直す」の遅延セグメント木版を考えます。

セグメント木は、モノイドの配列に対して、1点更新、区間取得が $O(\log n)$ で実行できるデータ構造でしたが、遅延セグメント木は、より多くのメモリ領域を消費する代わりに、モノイドの配列に対して、区間更新、区間取得が $O(\log n)$ で実行できます。

区間更新はモノイドのモノイドへの作用

$M=(M, \cdot, e)$ を(可換とは限らない)モノイドとして、このモノイドの配列に対する区間更新を考えます。

Segment Tree のお勉強(2) | maspyのHP を参考に、モノイドによるモノイドへの作用として整理します。(maspy氏の記事は右作用だがここでは左作用を扱う)

モノイド $F=(F, \circ, \mathrm{id})$ がモノイド $M$ に左作用するとは、 $M$ のモノイド演算と compatible である演算

$$\cdot : F \times M \to M$$

が存在し、

1. 任意の $f \in F, x, y \in M$ に対して、 $f(x \cdot y) = f(x) \cdot f(y)$
2. 任意の $f, g \in F, x \in M$ に対して、 $(g \circ f) \cdot x = g \cdot (f \cdot x)$
3. 任意の $x \in M$ に対して、 $\mathrm{id} \cdot x = x$

が成り立つことを言います。この条件は、 $\mathrm{End}(M)$ をM上の自己準同型からなるモノイド(演算は合成) とした時、モノイド準同型

$$\phi: F \to \mathrm{End}(M)$$

を考えていることと同じです。今後、 $F$ の $M$ への作用を $f \cdot x$ と書いたり、準同型写像を使って $\phi(f)(x)$ と書いたりしますが、これら2つは同じものです。

今回は $F$ は非可換でも大丈夫な形で議論を進めます。

AC LibraryのLazy Segtree では $F$ が $\mathrm{End}(M)$ の部分モノイドとなる条件に似た形で記載されていますが、こちらも実質的には同じですね。

こう定めると、区間更新は $a = (a_0, \cdots, a_{n-1}) \in M^n, f \in F, 0 \le l < r \le n$ に対して、

$$a_i \gets f(a_i), \quad l \le i < r$$

と適用すること、と表記できます。

左作用でも右作用でも、好きな方で考えれば良いですが、作用の合成をプログラムとして記述する際には、作用が右なのか左なのかによって書き方が変わってくるので注意が必要ですね。

---

具体例: 区間アフィン変換・区間総和(非可換な $F$ の例)

抽象的な議論だけだと $F$ の非可換性がどこに効いているか掴みにくいので、具体例を一つ挙げます。競技プログラミングで頻出の「区間に $x \mapsto ax+b$ を適用し、区間の総和を求める」問題がちょうど良い例になっています。

モノイド $M$: 区間和と区間の要素数の組を持たせる必要があるので、

$$M = \mathbb{R} \times \mathbb{Z}_{>0}, \quad (s_1, c_1) \cdot (s_2, c_2) = (s_1 + s_2,\ c_1 + c_2), \quad e = (0, 0)$$

とします。葉ノードには $(a_i, 1)$ を格納し(値 $a_i$ と要素数 $1$)、内部ノードには子の和が自動的に格納されます。区間和だけでなく要素数も一緒に運ばないと、後述の作用 $\phi(f)$ が正しく定義できない点がポイントです。

モノイド $F$: アフィン変換 $f_{a,b}(x) = ax + b$ 全体に、関数合成を演算として入れます。

$$F = \lbrace f_{a,b} \mid a \in \mathbb{R}^\times, b \in \mathbb{R} \rbrace, \quad \mathrm{id} = f_{1,0}$$

合成則を計算すると、

$$f_{a_2,b_2} \circ f_{a_1,b_1} = f_{a_2 a_1,\ a_2 b_1 + b_2}$$

となります。これは非可換です。実際 $a_1 \ne a_2$ のとき、

$$f_{a_2,b_2} \circ f_{a_1,b_1} \ne f_{a_1,b_1} \circ f_{a_2,b_2}$$

(左辺の $a$ 成分は $a_2 a_1$、右辺は $a_1 a_2$ で一致しますが、$b$ 成分は $a_2 b_1 + b_2$ 対 $a_1 b_2 + b_1$ となり、一般には一致しません)。具体的に $f_{2,1}, f_{3,0}$ を取ると、

$$f_{2,1} \circ f_{3,0} = f_{6, 1}, \qquad f_{3,0} \circ f_{2,1} = f_{6, 3}$$

で、確かに異なります。

作用 $\phi: F \to \mathrm{End}(M)$:

$$\phi(f_{a,b})(s, c) = (as + bc,\ c)$$

要素数 $c$ に応じて $b$ を $c$ 倍して足すことで、「区間内の $c$ 個の要素それぞれに $b$ を足す」効果を、和 $s$ の更新一発で表現しています。

作用の公理を確認すると、

• 準同型性 $\phi(f)(x \cdot y) = \phi(f)(x) \cdot \phi(f)(y)$: $x=(s_1,c_1), y=(s_2,c_2)$ に対し、両辺とも $(a(s_1+s_2)+b(c_1+c_2),\ c_1+c_2)$ となり一致。
• 合成との整合性 $\phi(g \circ f) = \phi(g) \circ \phi(f)$: $g=f_{a_g,b_g}, f=f_{a_f,b_f}$ とすると、 $$\phi(g\circ f)(s,c) = (a_g a_f, s + (a_g b_f + b_g) c,\ c)$$ $$\phi(g)(\phi(f)(s,c)) = \phi(g)(a_f s + b_f c,\ c) = (a_g(a_f s + b_f c) + b_g c,\ c)$$展開すると両者は一致します。ここで合成の順序を保つ必要があることが、$F$ の非可換性が本質的に効いてくる箇所です。

非可換な $F$ では、あるノードに複数の作用が「後から追加される」順番によって最終的な効果が変わります。例えば、あるノードにまず $f_{2,1}$ を適用した後に $f_{3,0}$ を適用したい場合、蓄積すべき合成後の作用は $u_\tau \gets f_{3,0} \circ u_\tau$ であり、$u_\tau \circ f_{3,0}$ ではありません(apply の疑似コードで u[τ] ← f ∘ u[τ] となっているのはこのため)。

もし $F$ が可換なら合成順序を気にせず値を先に評価してから作用を後回しにする最適化([いかたこ]記事の指摘)ができますが、非可換な今回のケースではそれができず、apply が子への再帰の前に必ず pushdown を呼んで「今蓄積されている作用を、追加する前に子へ確定させておく」必要があります(後ほど証明の中で出てきます)。

---

遅延セグメント木の状態空間

$n = 2^d$ の深さのセグメント木の状態空間は、 深さ $d$ の完全二分木のノード集合 $T_d$ に対してモノイドを割り当て、親が子の積になっているという局所的な条件を課すものでした。

$$\mathrm{Seg}_d(M) = \lbrace v \in M^{T_d} \mid v_\tau = v_{\mathrm{lch}(\tau)}\cdot v_{\mathrm{rch}(\tau)} \quad (\forall h(\tau) > 0) \rbrace$$

さらに、同型を通じて $\mathrm{Seg}_d(M)$ をモノイドの配列 $M^n$ と同一視していました。

遅延セグメント木では、「値の適用は必要な時にする」スタンスなので、木側の配列として、以前のような局所条件を課さない単なる直積集合をまず考えます。

$$\mathrm{St}_d(F, M) = F^{T_d} \times M^{T_d}$$

$\mathrm{Val}_d(M) = M^{T_d}$ が(部分的に作用を適用された)値を保持しておく木、 $\mathrm{Op}_d(F) = F^{T_d}$ が $M$ に適用すべき作用を必要な時まで保持しておく木に対応します。

$\mathrm{Op}_d(F)$ のノード $u_\tau$ には、 $\mathrm{Val}_d(M)$ の $v_\tau$ より下の子ノードたちに将来的に適用したい作用素を保持させます。

記号の準備

ノード $\tau$ の親を $\mathrm{par}(\tau)$ で表します。各ノード $\tau$ に対し、根から $\tau$ の親までの作用を合成したものを $L_\tau$ で表します。つまり、 $L_\mathrm{root} = \mathrm{id}$, $\tau'= \mathrm{par}(\tau)$ である時、 $L_\tau = L_{\tau'} \circ u_{\tau'}$ として再帰的に定義するものです。

セグメント木の時は、各ノードにそれぞれ区間に対応する計算結果がそのまま格納されており、真の値を読み出す $\pi_d$ は、単に木の葉への制限でした。 ところが遅延セグメント木の場合は、 $\mathrm{Op}(F)_d$ に残っている作用を $\mathrm{Val}_d(M)$ に適用しないと真の値が分かりません。

ノードに対応する真の値を

$$\mathrm{eval}_\tau = L_\tau \cdot v_\tau = \phi(L_\tau) (v_\tau)$$

で定義します。記号の濫用ですが、配列の真の値を読み出す関数

$$\mathrm{eval}: \mathrm{St}_d(F, M) \to M^n$$

を

$$\mathrm{eval}(u, v)_i = \mathrm{eval}_{\mathrm{Leaf}_i}$$

で定義します。

実装

次に疑似コードを用いて実装を確認します。

遅延セグメント木の初期化

• モノイド $M$ 側: 全ての $i$ に対して $a_i = e$, $\mathrm{Val}_d(M)$ の全ノードで $v_\tau \gets e$ とします。
• 作用するモノイド $F$ 側: 全ての $i$ に対して $f_i = \mathrm{id}$, $\mathrm{Op}_d(F)$ の全ノードで $u_\tau \gets \mathrm{id}$ とします。

pushdown: 蓄積されている作用の子への伝播

更新、取得関数を考える前に、遅延セグメント木で初めて出てくる「ノードに蓄積されている作用を子に伝播させる」操作を定義します。この操作はユーザーからは直接呼び出されません。疑似コードでは以下のようになります。

pushdown(τ):
  if h(τ) = 0: # 葉の場合
    return
  v[lch(τ)] ← φ(u[τ])(v[lch(τ)])
  v[rch(τ)] ← φ(u[τ])(v[rch(τ)])
  u[lch(τ)] ← u[τ] ∘ u[lch(τ)]
  u[rch(τ)] ← u[τ] ∘ u[rch(τ)]
  u[τ] ← id # ノードの作用をクリア

ここで h はノードの高さを返す関数です。

apply(l, r, f): 区間更新

set(i, c) の遅延セグメント木バージョンである apply(l, r, f) を定義します。

apply(l, r, f, τ):
  if seg(τ) ∩ [l, r) = ∅:
    return
  if seg(τ) ⊆ [l, r):
    v[τ] ← φ(f)(v[τ]) # 左作用
    u[τ] ← f ∘ u[τ] # 関数の合成
    return
  pushdown(τ) # 部分的に適用が必要な場合は、蓄積されている作用を子に伝播
  apply(l, r, f, lch(τ))
  apply(l, r, f, rch(τ))
  v[τ] ← v[lch(τ)] · v[rch(τ)]

apply(l, r, f) をルートに対する更新 apply(l, r, f, τ_root) として定義します。

query(l, r): 区間 [l, r) の総積

クエリについては、以前とほぼ同じ実装で、子の値の積を求める前に作用の伝播をする所だけが違います。

query(l, r, τ):
  if seg(τ) ∩ [l, r) = ∅:
    return e # Mの単位元
  if seg(τ) ⊆ [l, r):
    return v[τ]
  pushdown(τ)
  return query(l, r, lch(τ)) · query(l, r, rch(τ))

pushdown, apply をよく読むと、 $v_\tau$ の内容は $u_\tau$ にすでに適用されていることがわかるので、return v[τ] するときには pushdown(τ) を呼ぶ必要はありません。

query(l, r) をルートに対する更新 query(l, r, τ_root) として定義します。

実装に対応する数学的写像

pushdown, apply, query が表す数学的な写像を次のような記号で表します。ここはセグメント木の記事では少し適当にごまかしていた所ですね。

$$⟦\mathrm{pushdown}(\tau) ⟧: \mathrm{St}_d(F, M) \to \mathrm{St}_d(F, M)$$$$⟦\mathrm{apply}([l, r), f, \tau) ⟧: \mathrm{St}_d(F, M) \to \mathrm{St}_d(F, M)$$$$⟦\mathrm{query}([l, r), \tau) ⟧: \mathrm{St}_d(F, M) \to \mathrm{St}_d(F, M) \times M$$

query は潜在空間を更新するので値域は $M$ にはなりません。関数型言語で副作用を扱うときの「Stateモナド」に相当します。

$\mathrm{state}, \mathrm{val}$ は $\mathrm{St}_d(F, M) \times M$ の $\mathrm{St}_d(F, M), M$ への射影とします。

局所条件を考える

遅延セグメント木の状態空間では、「値の適用は必要な時にする」スタンスなので、モノイドの配列 $a \in M^n$ と木の状態が一対一に対応しないわけですが、実はセグメント木のような局所条件が存在します。遅延セグメント木の状態空間の元を $(u, v) \in F^{T_d} \times M^{T_d}$ で表します。

命題9. (局所条件)

$h(\tau) > 0$ を満たすノードについて、

$$v_\tau = u_\tau \cdot (v_{\mathrm{lch}(\tau)} \cdot v_{\mathrm{rch}(\tau)})$$

が成り立つことを局所条件という。局所条件は初期状態で成立している。

1. $⟦\mathrm{pushdown}(\tau) ⟧$ は局所条件を保つ。
2. $⟦\mathrm{apply}([l, r), f, \tau) ⟧$ は局所条件を保つ。
3. $\mathrm{state} \circ ⟦\mathrm{query}([l, r), \tau)⟧$ は局所条件を保つ。

証明.

関数の適用前の木を $s$, 適用後の木を $s'$ とする。葉でないノード $\sigma$ を任意に取って

$$v_\sigma(s') = u_\sigma(s') \cdot (v_{\mathrm{lch}(\sigma)}(s') \cdot v_{\mathrm{rch}(\sigma)}(s'))$$

が成立することを示す。

1. $⟦\mathrm{pushdown}(\tau) ⟧$ で変化するのは $u_\tau, u_{\mathrm{lch}(\tau)}, u_{\mathrm{rch}(\tau)}, v_{\mathrm{lch}(\tau)}, v_{\mathrm{rch}(\tau)}$ であることと対称性より、 $\sigma = \tau, \mathrm{lch}(\tau)$ の場合を調べれば十分である。 $\sigma = \tau$ の場合は、

$$\begin{align*} v_\tau(s') &= v_\tau(s) \\ &= u_\tau(s) \cdot (v_{\mathrm{lch}(\tau)}(s) \cdot v_{\mathrm{rch}(\tau)}(s)) \\ &= (u_\tau(s) \cdot v_{\mathrm{lch}(\tau)}(s)) \cdot (u_\tau(s) \cdot v_{\mathrm{rch}(\tau)}(s)) \\ &= \mathrm{id} \cdot (v_{\mathrm{lch}(\tau)}(s') \cdot v_{\mathrm{rch}(\tau)}(s')) \end{align*}$$

で、 $u_\tau(s') = \mathrm{id}$ より従う。

$\sigma = \mathrm{lch}(\tau)$ の場合は、

$$\begin{align*} v_\sigma(s') &= u_\tau(s) \cdot v_\sigma(s) \\ &= u_\tau(s) \cdot (u_\sigma(s) \cdot (v_{\mathrm{lch}(\sigma)}(s) \cdot v_{\mathrm{rch}(\sigma)}(s))) \\ &= (u_\tau(s) \circ u_\sigma(s)) \cdot (v_{\mathrm{lch}(\sigma)}(s) \cdot v_{\mathrm{rch}(\sigma)}(s)) \\ &= u_\sigma(s') \cdot (v_{\mathrm{lch}(\sigma)}(s') \cdot v_{\mathrm{rch}(\sigma)}(s')) \end{align*}$$

より成り立つ。

2. $h(\tau)$ の高さに関する帰納法で示す。 $\mathrm{seg}(\tau) \cap [l, r) = \emptyset$ の時は何も変化しないので自明。 $\mathrm{seg}(\tau) \subseteq [l, r)$ の時は、1. と同様の議論で証明できるので、それ以外の部分被覆となる場合を考える。1. により pushdown で局所条件が保存されることがわかるので、$s$ を pushdown 後の状態に取り替えてよい。

applyの影響範囲を考えると、 $\sigma$ が $\tau$ もしくは $\tau$ の真の子孫の場合のみ考えれば良いが、 $\tau$ の真の子孫の場合は帰納法の仮定より成立しているから、 $\sigma = \tau$ の場合を考えれば十分である。pushdown 後の状態では $u_\tau = \mathrm{id}$ だから、lch, rchを更新する際の影響範囲から $v_\tau(s') = v_{\mathrm{lch}(\tau)}(s') \cdot v_{\mathrm{rch}(\tau)}(s')$ と最後に更新していることから分かる。

3. 木の状態が変わるのは途中で pushdown を呼ぶ時だけなので、1.より成り立つ。

以上により示された。$\blacksquare$

命題9により、遅延セグメント木の潜在空間を

$$\mathrm{LazySeg}_d(F, M) =\{(u, v) \in \mathrm{St}_d(F, M) \mid v_\tau = u_\tau \cdot (v_{\mathrm{lch}(\tau)} \cdot v_{\mathrm{rch}(\tau)}), (\forall \tau, h(\tau) > 0) \} \subseteq \mathrm{St}_d(F, M)$$

に置き換えることができる。記号の濫用だが、

$$⟦\mathrm{pushdown}(\tau) ⟧: \mathrm{LazySeg}_d(F, M) \to \mathrm{LazySeg}_d(F, M)$$$$⟦\mathrm{apply}([l, r), f, \tau) ⟧: \mathrm{LazySeg}_d(F, M) \to \mathrm{LazySeg}_d(F, M)$$$$⟦\mathrm{query}([l, r), \tau) ⟧: \mathrm{LazySeg}_d(F, M) \to \mathrm{LazySeg}_d(F, M) \times M$$

で表し、以後は局所条件が成り立った状態の木のみ扱う。

命題9の系として、eval に対しての局所条件を示すことができます。

系10. (evalの局所条件)

$h(\tau) > 0$ のとき、

1. $\mathrm{eval}_\tau = \mathrm{eval} _{\mathrm{lch}(\tau)} \cdot \mathrm{eval} _{\mathrm{rch}(\tau)}$.
2. $\mathrm{eval}_\tau = \prod_{i \in \mathrm{seg}(\tau)} \mathrm{eval}_i$.

証明.

1. $$\begin{align*} \mathrm{eval}_{\mathrm{lch}(\tau)} \cdot \mathrm{eval}_{\mathrm{rch}(\tau)} &= ((L_\tau \circ u_\tau) \cdot v_{\mathrm{lch}(\tau)}) \cdot ((L_\tau \circ u_\tau) \cdot v_{\mathrm{rch}(\tau)}) \\ &= L_\tau \cdot (u_\tau \cdot (v_{\mathrm{lch}(\tau)} \cdot v_{\mathrm{rch}(\tau)})) \\ &= L_\tau \cdot v_\tau \\ &= \mathrm{eval}_\tau \end{align*}$$

   より従う。

2. 1. を使った帰納法で示せる。$\blacksquare$

真の値が変わらないこと

遅延セグメント木では query で値を読み出す際にも上側で pushdown が呼び出され木の状態が裏で変化します。この時、 $\mathrm{eval}$ で読み出す値が変化しないことを示します。

命題11: pushdown は eval を保つ

$\tau \in T_d$ を任意のノードとする。このとき、

$$\mathrm{eval} \circ ⟦\mathrm{pushdown}(\tau) ⟧ = \mathrm{eval}: \mathrm{LazySeg}_d(F, M) \to M^n$$

が成り立つ。

証明. $s = (u,v) \in \mathrm{LazySeg}_d(F,M), s' = ⟦ \mathrm{pushdown}(\tau) ⟧ (s)$ とする。

より広く、任意のノード $\sigma \in T_d$ に対して $\mathrm{eval}_\sigma(s') = \mathrm{eval}_\sigma(s)$ が成立することを証明する。

$⟦\mathrm{pushdown}(\tau) ⟧$ で変化するのは $u_\tau, u_{\mathrm{lch}(\tau)}, u_{\mathrm{rch}(\tau)}, v_{\mathrm{lch}(\tau)}, v_{\mathrm{rch}(\tau)}$ だったことを思い出し、 $\sigma$ と $\tau$ の位置関係で4通りに場合分けする。

ケースA: $\tau$ が $\sigma$ の祖先でない（ $\sigma \ne \tau$ かつ $\tau \notin \lbrace \sigma$ の祖先 $\rbrace$ ）

$v_\sigma$ は変化せず、 $L_\sigma$ も $\sigma$ の祖先の $u$ の合成なので、 $\mathrm{eval}_\sigma(s)$ は変化しない。

ケースB: $\sigma = \tau$

$⟦\mathrm{pushdown}(\tau) ⟧$ では $v_\tau$ は変化しない。根から $\tau$ の親までの作用を合成したものが $L_\tau$ なので、 $u_\tau$ の更新は影響せず、 $L_\tau(s') = L_\tau(s)$ となることから従う。

ケースC: $\sigma = \mathrm{lch}(\tau), \mathrm{rch}(\tau)$

pushdownの定義より、

$$\begin{align*} u_\tau^{\text{old}} &:= u_\tau(s),\\ u_\sigma^{\text{new}} &:= u_\sigma(s') = u_\tau^{\text{old}}\circ u_\sigma(s),\\ v_\sigma^{\text{new}} &:= v_\sigma(s') = \phi(u_\tau^{\text{old}})(v_\sigma(s)),\\ u_\tau^{\text{new}} &:= u_\tau(s') = \mathrm{id} \end{align*}$$

である。

$$L_\sigma(s) = L_\tau(s) \circ u_\tau(s) = L_\tau(s) \circ u_\tau^{\text{old}}$$

で、ケースBより $L_\tau(s') = L_\tau(s)$ だから、

$$\mathrm{eval}_\sigma(s) = L_\sigma(s) \cdot v_\sigma(s) = (L_\tau(s) \circ u_\tau^{\text{old}}) \cdot v_\sigma(s) = L_\tau(s) \cdot (u_\tau^{\text{old}} \cdot v_\sigma(s))$$

となる。最後の変形で $(g \circ f) \cdot x = g \cdot (f \cdot x)$ を使った。

一方、

$$\begin{align*} \mathrm{eval}_\sigma(s') &= L_\sigma(s') \cdot v_\sigma^{\text{new}}\\ &= (L_\tau(s') \circ \mathrm{id}) \cdot v_\sigma^{\text{new}}\\ &= L_\tau(s) \cdot (u_\tau^{\text{old}} \cdot v_\sigma(s)) \end{align*}$$

なので、$\mathrm{eval}_\sigma(s') = \mathrm{eval}_\sigma(s)$ となる。

ケースD: $\sigma$ が $\mathrm{lch}(\tau)$ または $\mathrm{rch}(\tau)$ の真の子孫

対称性より、 $\sigma$ が $\mathrm{lch}(\tau)$ の真の子孫場合のみ示せば十分である。

$v_\sigma$ は変化しないので、 $L_\sigma(s') = L_\sigma(s)$ を示せば十分。 $L_\sigma(s)$ の構成から、変化しない部分を省略して

$$L_\sigma(s) = (\cdots ((\cdots \circ u_\tau(s)) \circ u_{\mathrm{lch}(\tau)}(s)) \circ \cdots$$

と表せ、同様に

$$L_\sigma(s') = (\cdots ((\cdots \circ \mathrm{id}) \circ (u_\tau(s) \circ u_{\mathrm{lch}(\tau)}(s))) \circ \cdots$$

であり、 $F$ のモノイドとしての単位則、結合則を使うことで、これら二つが一致することがわかる。$\blacksquare$

次に、 apply の正当性を示す、と行きたいところなのですが、普通に示そうとすると $F$ が可換でなくては証明が回らないように見える部分が出てきます。

実は apply での実行中、再帰的に子の apply を呼び出す前に pushdown を呼んでいるのがミソです。遅延評価セグメント木 [いかたこのたこつぼ] で $F$ が可換なら更新前の評価を省ける、と書いているのがまさにこれと対応します。

補題12

apply(l, r, f, τ) が呼び出された直後の木の状態を $s_\tau$ とする。 この時、 $L_\tau(s_\tau) = \mathrm{id}$ が成立する。

証明. $\mathrm{root}$ から $\tau$ への深さに関する帰納法で示す。

$\tau = \mathrm{root}$ の時、定義より明らか。

$\tau \ne \mathrm{root}$ のとき、 $\tau' = \mathrm{par}(\tau)$ とすると、帰納法の仮定より $L_{\tau'} = \mathrm{id}$ 。apply(l, r, f, τ) は apply(l, r, f, τ') の実行中にのみ呼び出され、かつ pushdown(τ') の直後に呼び出されたと考えて良い。( $\tau = \mathrm{rch}(\tau')$ の場合は、先に呼ばれる apply(l, r, f, lch(τ')) は $\tau$ の祖先の $u, v$ を変化させない。) つまり、pushdown(τ') をして $u_{\tau'} = \mathrm{id}$ になった状態なので、

$$L_\tau = L_{\tau'} \circ u_{\tau'} = \mathrm{id} \circ \mathrm{id} = \mathrm{id}$$

より $\tau$ の場合も成り立つ。$\blacksquare$

applyは、 配列側の「区間に一様作用」と一致することを示しましょう。

命題13 (applyの妥当性)

$s \in \mathrm{LazySeg}_d(F, M)$ を潜在空間の状態、 $\tau$ を $L_\tau(s) = \mathrm{id}$ を満たすノードとする。 $s' = ⟦\mathrm{apply}([l, r), f, \tau) ⟧(s)$ とすると、

$$\mathrm{eval}(s')_i = \begin{cases}f \cdot \mathrm{eval}(s)_i & i \in \mathrm{seg}(\tau) \cap [l, r)\\ \mathrm{eval}(s)_i & i \notin \mathrm{seg}(\tau) \cap [l, r)\end{cases}$$

証明. $h(\tau)$ の高さに関する帰納法。

$i \notin \mathrm{seg}(\tau)$ のとき、 $\mathrm{eval}(\tau)_i$ の計算に利用される $\mathrm{Leaf}_i$ までの経路は影響を受けない。よって、 $i \in \mathrm{seg}(\tau)$ の場合を考えれば良い。

$\mathrm{seg}(\tau) \cap [l, r) = \emptyset$ のとき、 $s' = s$ より明らか。

$\mathrm{seg}(\tau) \subseteq [l, r)$ の時、 $L_\tau(s') = L_\tau(s) = \mathrm{id}$ である。 $\tau$ の部分木の葉 $\mathrm{Leaf}_i$ に対して、 $L_{\mathrm{Leaf}_i}$ を $\tau$ より上の部分と $\tau$ を含む $\tau$ より下の部分に分けると、 $F$ の結合則を使って括弧の順番を入れ替えることで、

$$L_{\mathrm{Leaf}_i}(s) = L_\mathrm{\tau}(s) \circ (u_\tau(s) \circ B(s))$$

と分解できる。ここで、 $B$ は経路に存在する $\tau$ の子から、 $\mathrm{par}(\mathrm{Leaf}_i)(s)$ までの $u$ の合成。 $L_\tau(s) = \mathrm{id}$ を使って、 $L_{\mathrm{Leaf}_i}(s) = u_\tau(s) \circ B(s)$.

同様に、

$$\begin{align*} L_{\mathrm{Leaf}_i}(s') &= L_\mathrm{\tau}(s') \circ (u_\tau(s') \circ B(s'))\\ &= u_\tau(s') \circ B(s')\\ &= (f \circ u_\tau(s)) \circ B(s)\\ &= f \circ L_{\mathrm{Leaf}_i}(s). \end{align*}$$

$v_{\mathrm{Leaf}_i}(s') = v_{\mathrm{Leaf}_i}(s)$ だから、

$$\begin{align*} \mathrm{eval}(s')_i &= L_{\mathrm{Leaf}_i}(s') \cdot v_{\mathrm{Leaf}_i}(s')\\ &= (f \circ L_{\mathrm{Leaf}_i}(s)) \cdot v_{\mathrm{Leaf}_i}(s)\\ &= f \cdot (L_{\mathrm{Leaf}_i}(s) \cdot v_{\mathrm{Leaf}_i}(s))\\ &= f \cdot \mathrm{eval}(s)_i\\ \end{align*}$$

となり従う。

$\mathrm{seg}(\tau) \cap [l, r) \neq \emptyset, \mathrm{seg}(\tau) \nsubseteq [l, r)$ の時、 pushdown(τ), apply(l, r, f, lch(τ)), apply(l, r, f, rch(τ)), v[τ] ← v[lch(τ)] · v[rch(τ)] が実行される。

命題11より $⟦\mathrm{pushdown}(\tau) ⟧$ は全てのノードの $\mathrm{eval}$ を保つ。 pushdown(τ) 後の状態を $\tilde{s}$ とすると、$u_\tau(\tilde{s}) = \mathrm{id}, L_\tau(\tilde{s}) = L_\tau(s) = \mathrm{id}$ より、

$$L_{\mathrm{lch}(\tau)}(\tilde{s}) = L_\tau(\tilde{s}) \circ u_\tau(\tilde{s}) = \mathrm{id} \circ \mathrm{id} = \mathrm{id}.$$

$\mathrm{rch}$ も同様。帰納法の仮定を高さ $h(\tau)-1$ の $\mathrm{lch}(\tau), \mathrm{rch}(\tau)$ に適用して、それぞれの再帰呼び出し後、その部分木の葉について主張が成りたつ。$\mathrm{seg}(\tau)=\mathrm{seg}(\mathrm{lch}(\tau))\sqcup\mathrm{seg}(\mathrm{rch}(\tau))$（非交和）なので、$\tau$ の部分木全体の葉について主張が成立する。 $\blacksquare$

命題13を根ノードに対して適用することで、apply により期待通りの適用ができることがわかります。

補題14

query(l, r, τ) が呼び出された直後の木の状態を $s_\tau$ とする。 この時、 $L_\tau(s_\tau) = \mathrm{id}$ が成立する。

証明. $\mathrm{root}$ から $\tau$ への深さに関する帰納法で示す。

$\tau = \mathrm{root}$ の時、定義より明らか。

$\tau \ne \mathrm{root}$ のとき、 $\tau' = \mathrm{par}(\tau)$ とすると、帰納法の仮定より $L_{\tau'} = \mathrm{id}$ 。query(l, r, τ) は query(l, r, τ') の実行中にのみ呼び出され、かつ pushdown(τ') の直後に呼び出されたと考えて良い。( $\tau = \mathrm{rch}(\tau')$ の場合は、先に呼ばれる query(l, r, lch(τ')) は $\tau$ の祖先の $u, v$ を変化させない。) つまり、pushdown(τ') をして $u_{\tau'} = \mathrm{id}$ になった状態なので、

$$L_\tau = L_{\tau'} \circ u_{\tau'} = \mathrm{id} \circ \mathrm{id} = \mathrm{id}$$

より $\tau$ の場合も成り立つ。　$\blacksquare$

命題15 (queryの妥当性)

$s \in \mathrm{LazySeg}_d(F, M)$ を潜在空間の状態、 $\tau$ を $L_\tau(s) = \mathrm{id}$ を満たすノードとする。

1. $(\mathrm{val} \circ ⟦\mathrm{query}([l, r), \tau) ⟧)(s) = \prod_{i\in \mathrm{seg}(\tau) \cap [l, r)} \mathrm{eval}_i(s)$
2. $(\mathrm{eval} \circ \mathrm{state} \circ ⟦\mathrm{query}([l, r), \tau) ⟧)(s) = \mathrm{eval}(s)$

が成り立つ。

証明.

1. 木の高さに関する帰納法。補題14により、途中で再起的に計算が呼び出される部分木の $L$ は自明。 $\mathrm{seg}(\tau) \cap [l, r) = \emptyset$ のとき、両辺 $e$ より明らか。 $\mathrm{seg}(\tau) \subseteq [l, r)$ のときは、$L_\tau(s) = \mathrm{id}$ より $v_\tau = \mathrm{eval}_\tau$ だから、系10 2. より従う。$\mathrm{seg}(\tau) \cap [l, r) \neq \emptyset, \mathrm{seg}(\tau) \nsubseteq [l, r)$ のときは、pushdown により部分木の $L$ が自明になるので帰納法の仮定が使えることから従う。

2. query 中に木の状態が変化するのは pushdown のみで、pushdown が eval を変化させないことから従う。　$\blacksquare$