Namaran

Code daily. Without assist.

2026-09-22

segtree_query.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 range_min(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]);
        }
        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, 7, 4];
    let n = a.len();
    let tree = build(&a);
    println!("{}", range_min(&tree, n, 4, 8));
}

セグメント木で区間[l, r)の最小値を求めるつもりのrange_minです。入力はa = [5, 2, 8, 1, 9, 3, 7, 4]・range_min(&tree, 8, 4, 8)(a[4..8] = [9, 3, 7, 4]の最小値)。いまの出力は1ですが、本来の出力は3です。何が問題で、どう直せばよいでしょうか?

Answer

lが奇数のとき、そのノードtree[l]を答えに取り込んだあとlを1つ右へ進める(l += 1)のを忘れています。進めないままl /= 2するので、本来区間の外側にあるはずの親ノードまで区間の内側として扱われてしまいます。range_min(&tree, 8, 4, 8)ではl = 12, r = 16から始まり、2階層縮めてl = 3, r = 4になった時点でlは奇数なのでtree[3] = 3(a[4..8]の最小値)を正しく取り込みますが、lを進めないままl /= 2するとl = 1になり、これは木全体の根です。次のループでl = 1が奇数と判定されてtree[1] = 1(a全体の最小値)まで答えに取り込んでしまい、本来関係ない範囲外の値のせいで結果が3ではなく1になります。直し方は、取り込んだ後にlを1つ進める行を追加するだけです:

if l % 2 == 1 {
    res = res.min(tree[l]);
    l += 1;
}