双対セグメント木という概念について

注意: この記事は概念の整理のために新しい名前を導入するだけであり、新しい木を提案するものではない

定義

通常の遅延伝搬セグメント木の作用素側のみを取り出してできる木を「双対セグメント木」と呼ぶ。

説明

通常のセグメント木は次の操作をそれぞれ $O(\log n)$ で行うデータ構造であった:

点更新: 値 $b$ と添字 $i$ が与えられ、 $a_i \gets b$ と更新する
区間取得: 区間 $[l, r)$ が与えられ、 $a_l \cdot a _ {l+1} \cdot \dots \cdot a _ {r-1}$ を計算する

双対セグメント木は次の操作をそれぞれ $O(\log n)$ で行うデータ構造である:

区間更新: 作用素 $f$ と区間 $[l, r)$ が与えられ、 $x_l \gets f(x_l) \; ; \; x _ {l+1} \gets f(x _ {l+1}) \; ; \; \dots \; ; \; x _ {r-1} \gets f(x _ {r-1})$ と更新する
点取得: 添字 $i$ が与えられ、 $x_i$ を計算する

ただし、列 $(x_0, x_1, \dots, x _ {k-1})$ の要素は集合 $X$ の要素であり、作用はモノイド $(F, \circ, \mathrm{id})$ による作用 $\star : F \times X \to X$ であるとする。つまり、次を満たす必要がある:

($(F, \circ, \mathrm{id})$ がモノイドであること)
作用に関する単位元 $\mathrm{id} \star x = x$
作用に関する結合律 $(f \circ g) \star x = f \star (g \star x)$

見れば分かるように、双対セグメント木の要件は通常の遅延伝搬セグメント木の要件より真に弱いものとなっている。

なにが嬉しいのか

双対セグメント木の利点として、以下の2点が挙げられる:

不必要な要素について考えなくてよいので議論が単純になる。
実装が定数倍高速になる。

特に前者について、補足で述べるように遅延伝搬セグメント木での再現は自明ではないので、この利点は十分に大きい。よってこの木に個別の名前を付けることには価値があると言える。

実装例

https://github.com/kmyk/competitive-programming-library/blob/master/data-structure/dual-segment-tree.inc.cpp ^archive.org

利用例: 区間各点代入

集合 $X$ の要素の列 $(x_0, x_1, \dots, x _ {k-1})$ があるとする。値 $b$ を使って区間 $[l, r)$ 中の各点 $x_i$ (ただし $i \in [l, r)$) を $x_i \gets b$ として更新する操作を考えよう。

これは双対セグメント木を用いて $F = X \cup \{ e \}$ のようにして容易に実現できる。恒等関数のための $1$ 点を加える (実装においては std::optional<T> などを使う) 必要があることには注意したい。

この用途に関しては初期化配列や文字列の範囲書き込みという形でも知られている (参考: https://qiita.com/kgoto/items/0251e442292d8ebc1f3d ^archive.org, https://qiita.com/kgoto/items/e7e83e51d4c4fcc72af9 ^archive.org)

利用例: 区間各点 $n$ 乗

環 $R$ の要素の列 $(a_0, a_1, \dots, a _ {k-1})$ があるとする。自然数 $n$ を使って区間 $[l, r)$ 中の各点 $a_i$ (ただし $i \in [l, r)$) を $a_i \gets a_i^n$ として更新することを考えよう。

これも双対セグメント木を用いれば $F = (\mathbb{N}, \cdot, 1)$ として実現できる。

例として先に挙げた区間代入は、整数列などを対象とするときは線形関数と区間和を用いた遅延伝搬セグメント木で再現することも可能だが、こちらはそのような再現は不可能であり、双対セグメント木を用いることが本質的であることに注意したい。

補足: 通常の遅延伝搬セグメント木を用いての再現について

双対セグメント木の要件は通常の遅延伝搬セグメント木の要件より真に弱いものとなっていた。しかし、これを用いての再現は自明ではない。

もし遅延伝搬セグメント木の区間取得の結果が正しいものでなくなってもよいならば、遅延伝搬セグメント木の実装を使って双対セグメント木を再現できる。これはまったく適当なモノイドを与えてやればよい。しかしこれは「実装を流用できる」というのみであり「遅延伝搬セグメント木を用いて双対セグメント木を再現できる」と主張するにはいくらか不足がある。

区間取得の結果の正しさを保ちたいという要件があれば自明ではない。つまり、モノイド $(F, \circ, \mathrm{id})$ と集合 $X$ および作用 $\star : F \times X \to X$ が与えられたとき、遅延伝搬セグメント木の要件を満たすことのできるモノイド演算 $\cdot : X \times X \to X$ は常には存在しない。存在するための必要十分条件は、任意の作用素 $f \in F$ に対してある $x \in X$ が存在してそれが不動点 $f(x) = x$ になることである。もちろんこの条件は恒真ではない。

補足: 元にする木がセグメント木であることは本質的ではないことについて

省略

補足: 作用素はモノイドでなければならない

通常のセグメント木に乗る構造は圏とできたが、双対セグメント木に乗る構造を圏とすることはできない。

補足: 名前の選択について

この木を双対と呼ぶ例はひとつのみではあるが他にも見つけられた (http://tomabou.hatenablog.com/entry/2017/09/04/002836 ^archive.org) ので妥当と言ってよいだろう。

定義

説明