Namaran

Code daily. Without assist.

2026-09-22

segtree_trace.rs

fn build(a: &[i32]) -> Vec<i32> {
    let n = a.len();
    let mut tree = vec![i32::MAX; 2 * n];
    tree[n..].clone_from_slice(a);
    for i in (1..n).rev() {
        tree[i] = tree[2 * i].min(tree[2 * i + 1]);
    }
    tree
}

fn query(tree: &[i32], n: usize, mut l: usize, mut r: usize) -> i32 {
    let mut res = i32::MAX;
    l += n;
    r += n;
    while l < r {
        if l % 2 == 1 {
            res = res.min(tree[l]);
            l += 1;
        }
        if r % 2 == 1 {
            r -= 1;
            res = res.min(tree[r]);
        }
        l /= 2;
        r /= 2;
    }
    res
}

fn main() {
    let a = [5, 2, 8, 1, 9, 3];
    let n = a.len();
    let tree = build(&a);
    println!("{}", query(&tree, n, 1, 5));
}

このプログラムは何を出力するでしょうか?

Answer

1です。これは区間最小値を管理するセグメント木を、ノードへのポインタを持つ木構造ではなく、1本のVec<i32>に平らに詰め込んで表現したものです(Rustでは、親から子への所有権と、子から親を指し返す参照を同時に持つ木は借用のルール上素直には書けないため、こうした添字だけで親子関係を表す配列表現がよく使われます)。buildは元の配列aをtree[n..]に葉として置き、内部ノードtree[i]には子tree[2*i]・tree[2*i+1]の小さい方を下から順に詰めます。a = [5, 2, 8, 1, 9, 3]に対してtree = [_, 1, 1, 2, 1, 3, 5, 2, 8, 1, 9, 3](添字0は未使用)になります。query(&tree, 6, 1, 5)は半開区間[1, 5)、つまりa[1..5] = [2, 8, 1, 9]の最小値を求めます。l・rにnを足して葉の位置に揃えたあと、lが奇数(右の子)ならそのノードを答えに取り込んで1つ右へ、rが奇数なら1つ左に戻してから取り込み、最後にl・rをともに2で割って1つ上の階層へ上がる、をl < rの間繰り返します。a[1..5]の最小値は1なので、答えも1になります。