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

前回の記事では方法 1 について記述しました。
今回はそれを発展させた方法 2 について記述します。

方針

方法 2 では、方法 1 の状態からさらに、子ノードが 1 個のノードを省略します。
下図は、クエリ (1) によりインデックス $2,4,5,6$ の値が更新されたときの例です。
根は $[0,8)$ となります。

保持するノードを省略することで、メモリ使用量を削減します。
方法 1 とは大きく異なるのが、クエリ (1) において二分木にノードを追加するときの処理です。

例として、クエリ (1) によりまず葉 $2,4,5$ が追加されており、その次に葉 $6$ が追加される場合を考えましょう。
葉 $6$ が追加される前の状態は下図のようになっています。

根を出発して葉 $6$ を探索していきます。
$6$ を含まない区間 $[4,6)$ が見つかると、葉 $6$ とノード $[4,6)$ の (元の完全二分木における) 最小共通祖先 (lowest common ancestor; LCA) であるノード $[4,8)$ を挿入し、ノード $[4,6)$ と葉 $6$ をそれぞれ左右の子ノードに設定します。
この方法であれば、1 回のクエリ (1) において新たに追加されるノードはたかだか 2 個であることが保証されます。

これを一般化して、 $i \notin [L, R)$ を満たす葉 $i$ とノード $[L, R)$ の (元の完全二分木における) LCA を求めるには、次のようにビット演算を用います。
なお、& は AND、| は OR、^ は XOR、~ は補数の演算子をそれぞれ表します。

LCA を求める方法
L ^ i の最上位ビットのみを抜き出したものを f とする。
これは、LCA が表す範囲の長さの半分となる。
l := i & ~(f | (f - 1)) とすれば、LCA が表す範囲は $[l, l + 2f)$ となる。

整数に対して最上位ビットのみを抜き出すことは、次のようなビット演算でできます。

static int MaxBit(int x)
{
    x |= x >> 1;
    x |= x >> 2;
    x |= x >> 4;
    x |= x >> 8;
    x |= x >> 16;
    return x ^ (x >> 1);
}

.NET では、BitOperations.LeadingZeroCount メソッドからも求めることができます。

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

上記の方法を利用できる問題およびコードを示します。言語は C# です。

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

1 回のクエリ (1) において新たに追加されるノードはたかだか 2 個であることから、配列ベースの実装においては、クエリが $q$ 回実行される場合、サイズ $O(q)$ の配列を初期化すれば十分です。

まとめ

以上でセグメント木の定義域を拡張し、座標圧縮をせずにオンラインクエリの処理が可能になりました。

さて、二分探索木においてもこれに近い実装が可能で、平衡二分探索木にあるような回転が不要になります。これについてはまた後日投稿します。

作成したサンプル

AlgorithmSample (GitHub)

検証したバージョン

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

参照

履歴

2024.03.28 問題集に PAST 13 L を追加

Avant-Garde Code

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

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

方針

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

まとめ

作成したサンプル

検証したバージョン

参照

履歴