Wed Sep 09 2020

遅延セグメントツリーを学んだ

2020 年になってようやく遅延（伝播）セグメントツリーを知ったので解ける問題が増えて今嬉しい.

遅延セグメントツリーは一言で言えばこのようなもの. モノイド \(X\) と, それに対するモノイド作用 \(M\) があるときにこんなことが出来る. \(X\) の要素からなる長さ \(N\)の数列 \(x\) について,

1. 任意の添字区間 \(I\) に対して \(\prod_{i \in I} x_i\) を \(O(\log N)\) 程度で計算する
2. 任意の添字区間 \(I\) と（左）作用 \(m \in M\) について \(x_i \leftarrow m(x) ~(i \in I)\) という更新を \(O(\log N)\) 程度で行う

という2つの計算をサポートする. 特に2つ目の更新は区間に対して行えるのがただのセグメントツリーとの違い.

• プロコン用ライブラリ:
  • procon/seq.lazy_segment_tree

私が書いたライブラリは一般にモノイド作用つきモノイドについて定義できるようになっているので, 今の説明で言うところの \(X\) と \(M\) だけ問題に合わせたものを定義すればいつの間にか完成する.

• ちゃんとした説明:
  • aiura/monoidic-act-and-lazy-segment-tree

Range Maximum (Minimum) Query

整数の列 \(x\) について

• 区間取得: \(\sum_{i \in I} x_i\)
• 区間更新: \(x_i \leftarrow z\)

というタイプの問題を考える. 更新は区間と代入する値 \(z\) を決めたらその区間の中の値を \(z\) で上書きしてしまうタイプ.

まず \(X\) とその積は区間取得の方法をそのまま実装するだけ. 更新というのが作用に相当する. 作用の積は少し非自明だけど, 作用の合成を注意深く追えばいい.

• \(X = \mathbb Z\)
  • 積
    • \(x_1 \times x_2 := x_1 + x_2\)
  • 単位元
    • \(0 \times x = x \times 0 = x\)
• \(M = \mathbb Z + 1\)
  • 積
    • \(\ast \times n = n\)
    • \(m \times n = m\) (if \(m \ne \ast\))
  • 単位元
    • \(\ast \times m = m \times \ast = m\)

ここで \(M\) は左作用として定義している. また \(\mathbb Z + 1\) は整数集合と単集合 \(\{ \ast \}\) との直和のこと.

\(M\) の \(X\) に対する作用は \(m \in M, x \in X\) について

• \(\ast(x) = x\)
• \(m(x) = m\) (if \(m \ne \ast\))

この作用が数列の値の上書きを意味している. 特に \(\ast \in M\) は何も上書きしないということを表していて, 単位元としての役割を与えている. \(M\) の積だが, \(m(n(x)) = (m \times n)(x)\) を満たすような \(m \times n\) が定義できていれば正しい. 今回は値の上書きなので, 後から適用したものを優先していればいい.

区間への加算

先程は区間へ定数を代入するタイプだったが, それぞれに値を加算するタイプのものも見かける.

• 区間取得: \(\sum_{i \in I} x_i\)
• 区間更新: \(x_i \leftarrow x_i + z\)

すぐ思いつくのは次のようなものだ. \(X\) は先程と全く同じで良さそう. それから \(M\) は \(M=\mathbb Z\) で \(m(x) = m+x\) とでもしておけば動きそう. これは実は間違えている.

なぜなら, \(m(x_1 \times x_2) = m(x_1) \times m(x_2)\) というモノイド作用が満たすべき準同型を満たしていない.

例えば \(m\) が \(+1\) することを表してるとき, 各子ノードに \(+1\) したのに親ノードにも \(+1\) してるようなものだからだ. 親ノードは子ノードの値全ての和を表してるはずだから, 各子ノードに \(+1\) したなら, ノード数分だけ, 加算する必要が生じる.

じゃあ \(X\) にそのノード数まで情報として持たせればいい. つまり \(X\) はカバーする区間に含まれる値の和と区間の長さのペアにする.

• \(X = \mathbb Z \times \mathbb N\)
  • (和, 長さ)
  • 積
    • \((x_1, \ell_1) \times (x_2, \ell_2) := (x_1 + x_2, \ell_1 + \ell_2)\)
  • 単位元
    • \((0, 0)\)
• \(M = \mathbb Z\)
  • \(m \in M\) は \(+m\) することを表す
  • 積
    • \(m \times n = m + n\)
  • 単位元
    • \(0\)
  • 作用
    • \(m(x, \ell) = x + m \ell\)
      • ここが重要

長さ \(\ell\) の区間があって今そこの和が \(x\) のとき, この各値に \(m\) を足すと, 和は \(x + m \ell\). 当たり前ですね.

例題

AtCoder Library Practice Contest/ K - Range Affine Range Sum

• 区間取得: \(\sum_{i \in I} x_i\)
• 区間更新: \(x_i \leftarrow b x_i + c\)

今度は足すだけじゃなくて掛け算も入ってる. でもさっきのとほとんど同じ.

作用 \(m = (b, c) \in \mathbb Z \times \mathbb Z\) について,

• \(m(x, \ell) = bx + c\)

というのが実際の作用だし, \(M\) の積はこれを満たすように適切に定めるだけ.

AtCoder Library Practice Contest/ L - Range Affine Range Sum

どんな情報があれば転倒数がマージできるか考えればおのずと \(X\) が決まる.

区間 \(I_1\) を左に, \(I_2\) を右にしてマージするとき, 出来上がった区間の転倒数は, それぞれの転倒数はそのまま足して, 新たに出来る転倒というのは \(I_1\) に含まれる \(1\) の数と \(0\) の数との積, これを加える. 従って, まず \(0,1\) それぞれの個数と, 転倒数を情報として持っておけば良さそう.

さてこの問題における区間に対する更新というのが 0/1 のフリップ操作. フリップしたときに出来る転倒数は今述べた3つの情報だけからは分から無さそう. しかし, 「フリップしたら転倒する」数というのも転倒数と同じ計算量で計算できるに決まってるので, これも持っておけばいい. つまり, \(X\) はその区間における

• \(z =~\) \(0\) の個数
• \(o =~\) \(1\) の個数
• \(i =~\) 転倒数
• \(p =~\) 逆転倒数 (0/1 をフリップした場合の転倒数)

の組 \(x = (z,o,i,p)\). そして積は \[x_1 \times x_2 = (z_1, o_1, i_1, p_1) \times (z_2, o_2, i_2, p_2) = (z_1 + z_2, o_1 + o_2, i_1 + i_2 + o_1 z_2, p_1+p_2+o_2z_1)\] で定義される.

更新操作は簡単で, フリップするかしないかの2状態しかない. 「スリップする」をちょうど2回適用したときはもとに戻って「フリップしない」と等しいことに注意しよう.

\(\def\true{\mathrm{true}}\def\false{\mathrm{false}}\) \(M = \{\true, \false\}\) としておいて,

• 作用
  • \(\true(z,o,i,p) = (o,z,p,i)\) (交換する)
  • \(\false(x) = x\) (交換しない)

を定める.