動的セグメント木

動的セグメント木は必要なノードだけを作成することで、巨大（ $N ≫ 1 0^{5}$ ）な配列でもセグメント木を構築できるようにしたものです。

実装方針

高速化のために以下の方針を採用します：

ポインターではなくアリーナ¹で木をつくる
非再帰実装

また、簡単のために、追加の制約を課します：

Range<isize>で初期化し、区間幅は固定
単位元で初期化

実装例（動的セグメント木）

#![allow(unused)]
fn main() {
pub struct DynamicSegmentTree<Query>
where
    Query: Monoid,
{
    arena: Vec<Node<<Query as Monoid>::Set>>,
    range: Range<isize>,

    // save allocation cost
    reusable_stack: Vec<usize>,
}
}

Node<T>の詳細は後述します。

非可換モノイドでは要素の合成順が重要です。後述のように、正しい順序で要素を合成するためにスタックを使用します。 reusable_stackはスタックの長さが $⌈ lo g N ⌉$ で抑えられることを利用して、アロケーションコストを節約するためにあります。

計算量

区間幅を $N$ とし、ある時点での更新クエリの数を $Q$ とします。

	arena	range query	point update
time/space complexity	$Θ (Q)$	$O (lo g N)$	$O (lo g N)$

実装例

初期化子

seg_libにおいて動的セグメント木の区間は初期値で固定されます。 Range型は不正な区間（1..0など）を持つことができるため、これをケアする必要があります。区間幅がゼロの場合もまとめてrange.is_empty()で処理できます。

実装例（初期化子）

#![allow(unused)]
fn main() {
    pub fn with_capacity(range: Range<isize>, q: usize) -> Option<Self> {
        if range.is_empty() {
            None
        } else {
            // never panic: `range.len()` is always larger than 0
            let height = range.len().ilog2() as usize + 1;
            Some(Self {
                arena: Vec::with_capacity(q * height),
                reusable_stack: Vec::with_capacity(height * 4),
                range,
            })
        }
    }
}

seg_libはcrates.ioで公開しているため、返り値にOption型を取ることにしました。競プロなどではpanic!()するのもありです。

Tip

単位元以外の値で初期化することもできます。

可換モノイドの場合は簡単で、以下のようにしてモノイドに更新済みノード数を持たせるだけです。初期値をもつノードの数は区間幅 - 更新済みノード数で与えられるので、繰り返し自乗法などをもちいて $O (lo g N)$ で計算できます。

#![allow(unused)]
fn main() {
use seg_lib::{DynamicSegmentTree, ops::Add};

let mut dst = DynamicSegmentTree::<(/* operation */, Add<usize>)>::new(/* range */);
dst.point_update(/* index */, (/* value */, 1));
let (combined, n) = dst.range_query(/* sub range */);
}

非可換モノイドを扱う場合、計算順序を守るために、実装に踏み入る必要があります。ノードごとに $O (lo g N)$ かかるので、取得クエリ・更新クエリの計算量が $O (lo g^{2} N)$ に悪化します。または、動的遅延伝搬セグメント木を利用してもよいです。

ノード

動的セグメント木では必要最小限のノードを作成することで、空間計算量 $Θ (Q)$ を実現します。

通常のセグメント木のように、各ノードに対応する区間の途中結果をもつ場合、空間計算量が $O (Q lo g N)$ になってしまいます。対応する区間に更新されたノードが1つしかない場合にノードの作成を遅延することで、空間計算量を $Θ (Q)$ に削減できます。

実装例（初期化子）

#![allow(unused)]
fn main() {
struct Node<T> {
    index: isize,
    element: T,
    /// may be `None` if `combined == element`, avoiding `clone()`
    combined: Option<T>,

    left_ptr: Option<NonZeroUsize>,
    right_ptr: Option<NonZeroUsize>,
}
}

seg_libの動的セグメント木では区間幅を固定しているので、各ノードが持つ区間情報は暗黙的に与えられます。区間情報は根から子を辿る際に計算できるので、ノードには持ちません。
ノードに対応する区間の途中結果にはOption型を採用しました。これはトレイト境界<Query as Monoid>::Set: Cloneを回避するためです。
通常Option型は追加のフラグに8byte（64bitシステムの場合）利用しますが、Option<NonZero<T>>では0をNoneと扱う最適化が施されており、追加のメモリは必要ありません。 arenaの0要素目は根なので、子のインデックスは常に正です。

更新クエリ

range update

あるノードに対応する区間で2つめのノードが更新される場合、新たにノードを作成する必要があります。このとき、左の子のインデックス < 親のインデックス < 右の子のインデックスの関係を保持する必要があります。また、途中結果を帰りがけ順序で再計算する必要があります。ここで、reusable_stackを活用してアロケーションコストを節約します。

取得クエリ

動的セグメント木においてもっとも複雑な部分です。

観察

区間クエリが1つのノードに収まる場合と、2つのノードにまたがる場合で場合分けができます。

range query

タイプ1の場合、次に訪問するノードが右（左）の子ならば、合成順序は最後のノードよりも左（右）側です。また、訪問順序が早いノードほど外側にあることが分かります。 reusable_stackを活用することで、この順序を再現できます。

タイプ2の場合に左の子を祖先に持つノード群を合成することを考えます。 L1から始めて、次に外側のL3に進むので、内側にあるL2は答えに含まれます。 L1自身の持つノードは外側から合成します。 L3の次は内側のノードであるL4に進みます。 L4の配下は明示されていないので何とも言えませんが、L3のノードを合成する場合は一番外側からであることは保証されます。したがって、L3の持つノードへのポインター²をreusable_stackに格納します。

右側の子孫たちの合成順序で確認してみてください。 R1の次は内側に進むので、reusable_stackに格納します。 R2の次は外側に進むので、R3を右から合成し、R2を右から合成します。

`reusable_stack`における左右の区別

ここまでで、reusable_stackには0個以上のポインターが格納されています。ポインターはただのusizeなので、左右の区別をするために工夫をする必要があります。

ポインターはアリーナのインデックスであり、アリーナはVecです。実は、Vecの容量の最大値はisize::MAXと決まっています。たとえば、Vec::with_capacity()でisize::MAXより大きな容量を与えるとpanicします。したがって、usizeの最上位ビットをフラグとして利用できます。

実装例（左右の区別）

#![allow(unused)]
fn main() {
        while let Some(ptr) = self.reusable_stack.pop() {
            const MSB: usize = 1_usize.rotate_right(1);
            res = if ptr & MSB == 0 {
                <Query as Monoid>::combine(self.arena[ptr].get_element(), &res)
            } else {
                <Query as Monoid>::combine(&res, self.arena[!ptr].get_element())
            }
        }
}

resはタイプ2の場合の内側の計算結果です。

左側のノードへのポインターはそのまま、右側のノードへのポインターはビット反転してから、reusable_stackに格納しています。

配列上にノードを格納し、インデックスをポインター代わりにするテクニックのこと。キャッシュ効率が良く、所有権の管理が容易。 ↩
ノードのインデックスと区別するために、アリーナ上のインデックスをポインターと呼ぶことにします。 ↩

Keyboard shortcuts

Segment Tree Library Book