サイズ

セグメント木のサイズは、要素数を $N$ として $2^{⌈ l o g_{2} N ⌉ + 1}$ とかけます。末尾の余分な要素を除去して、n.next_power_of_two() + n + (n & 1)とすることもできます。サイズを偶数にしておくと実装が楽です。

さらに、サイズを $2 N$ にすることもできます。メモリの使用量が少なく、とくに $N = 2^{n} + 1$ のとき、使用するメモリの比はおよそ $4 : 3 : 2$ です。しかしながら、いくつかのアルゴリズムの実装が複雑になります。

segment tree

$N$ の立っているビットごとに完全二分木を作ることもできます。高々 $lo g N$ 個の木を管理する必要があるため、サイズは $2 N + O (lo g N)$ です。追加のメモリコストを支払う代わりに不正なセグメントができないため、実装がシンプルになる可能性があります。添え字を木と対応づけるためにはusize::MAX - (N - i).leading_zeros()などとすればよいです¹。ただし、サイズ $2^{k}$ の木が配列のk要素目に格納されています。

特別な場合

$N = 0, 2^{n}$ のとき、ビット演算をうまく使った実装が壊れることがあります。たとえば、i >>= i.trailing_zeros()などです。小さな $N$ について、網羅的に単体テストをすると、この種のバグを発見できます。

単体テスト

区間和クエリを確かめる場合、 $1$ で初期化してておくと、セグメントの和とサイズが一致する。

#![allow(unused)]
fn main() {
    #[test]
    fn ones() {
        const MAX_SIZE: isize = 200;
        const OFFSET: isize = 10;

        for size in 0..MAX_SIZE {
            let range_sum_query =
                SegmentTree::<Add<isize>>::from_iter(std::iter::repeat_n(1, size as usize));
            for start in 0..=size {
                for sum in -OFFSET..=size as isize + OFFSET {
                    assert_eq!(
                        range_sum_query.partition_end(start as usize, |&v| v <= sum),
                        (start + sum).clamp(start, size) as usize,
                        "size: {size}, start: {start}, sum: {sum}"
                    )
                }
            }
        }
    }
}

区間クエリの終端がNでないことが分かっている場合、(N - i).ilog2()とできます。 ↩

Keyboard shortcuts

Segment Tree Library Book

サイズ

特別な場合