Avant-Garde Code

アバンギャルド・コード is 前衛的算譜.

セグメント木の定義域を拡張する (1)

データ構造

概要

通常のセグメント木では、管理対象の列の項数 $n$ を固定して完全二分木を構築するため、初期化に時間計算量および空間計算量 $O(n)$ を要し、1 回のクエリあたり時間計算量 $O( \log n)$ を要する。したがって、 $n$ として利用できる値には計算機資源上の制限があり、列のインデックス (セグメント木の定義域) としてより大きな値を利用するには、オフラインクエリ (入力値がすべて予め与えられる) を前提として座標圧縮をする必要があった。

そこで本稿では、セグメント木の定義域を拡張し、例えば $[0, 2^{30})$ や $[0, 2^{62})$ のような範囲を利用できる方法について記述する。これにより、座標圧縮をせずにセグメント木のオンラインクエリ (入力値が逐次的に与えられる) を処理することができる。
次の 2 つの方法がある：

方法 1 : 完全二分木のノードのうち、各更新クエリで指定されたインデックスに対応する葉と、根を結ぶパス上のノードのみ保持する。
方法 2 : 方法 1 によるノードのうち、子ノードの個数が 1 のノードを保持しない。

導入

まず準備として、空間 $V$ に対し、二項演算 $*: V \times V \to V$ と単位元 $e$ のペアで特徴付けられるモノイドがあるとします。空間 $V$ の値としては実数、行列などが該当し、二項演算 $*$ としては加算、乗算、 $\max$ などが該当します。また、二項演算 $*$ の時間計算量は $O(1)$ であると仮定しておきます。

セグメント木は通常、項数 $n$ の列に対して区間の集計値を動的に求められるデータ構造である、と説明されると思います。厳密に書くと、次のような操作ができるデータ構造です：

$k$ を非負の整数とする。
項数 $n = 2^{k}$ の列 $(a_i \in V)_{0 \le i \lt n}$ およびモノイド $(*, e)$ に対し、初期値を $a_i = e \ (0 \le i \lt n)$ としたうえで、以下のクエリが任意に実行される。

(1) $a_i$ の値を更新する $(0 \le i \lt n)$
(2) $a_l * \cdots * a_{r-1}$ の値を取得する $(0 \le l \lt r \le n)$

初期化に時間計算量および空間計算量 $O(n)$ を要し、1 回のクエリあたり時間計算量 $O( \log n)$ を要する。

ここで初期化に要する時間計算量および空間計算量を $O(1)$ に改善する方法を考えていきます。
このページではまず、方法 1 について記述します。

方針

通常のセグメント木は、列の項数 $n$ を固定して、完全二分木を構築して初期化します。
下図は $n=8$ の例です。

方法 1 では、根は例えば $[0, 2^{30})$ を表すこととし、更新クエリ (1) が実行されたときのみ、指定されたインデックスに対応する葉ノードを追加します。このとき、完全二分木における根と葉を結ぶパス上のノードをすべて追加します。
初期状態ではノードを持ちません。

下図は、クエリ (1) によりインデックス $2,4,5,6$ の値が更新されたときの例です。

クエリ (1) が実行されていないインデックス $i$ については $a_i = e$ のままです。したがって、各ノードにおいて二項演算 $*$ により集計する際、左または右の子ノードが存在しない場合は、暗黙的に単位元 $e$ が設定されていると見なせばよいです。

以上の方針をノードベース (ノードをオブジェクトで表現する) で実装すれば、初期化に要する時間計算量および空間計算量は $O(1)$ で済みます。
なお、配列ベースで実装することも可能で、クエリが $q$ 回実行される場合は、サイズ $O(q \log n)$ の配列を初期化すればよいです。

問題集およびソースコード

上記の方法を利用できる問題およびコードを示します。言語は C# です。
これらのソースコードでは、定義域を $[-2^{30}, 2^{30})$ としています。

ABC 221 E では Range Sum Query (RSQ) に特化したコードを使うことができます。
加算はモノイドの中でも性質がよいため、RSQ のコードを簡略化できます。

次回は、方法 2 について記述します。

次回: セグメント木の定義域を拡張する (2)

作成したサンプル

AlgorithmSample (GitHub)

検証したバージョン

開発環境: C# 10, .NET 6
実行環境: C# 11, .NET 7 (AtCoder)

参照

Mermaid (グラフの作図)
セグメント木の定義域を拡張する (2)

履歴

2024.03.28 問題集に PAST 13 L を追加