Namaran

Code daily. Without assist.

2026-09-23

segtree_range_query.rs

enum Tree {
    Leaf(i32),
    Node(i32, Box<Tree>, Box<Tree>),
}

fn build(a: &[i32]) -> Tree {
    if a.len() == 1 {
        Tree::Leaf(a[0])
    } else {
        let mid = a.len() / 2;
        let left = build(&a[..mid]);
        let right = build(&a[mid..]);
        let m = min_of(&left).min(min_of(&right));
        Tree::Node(m, Box::new(left), Box::new(right))
    }
}

fn min_of(t: &Tree) -> i32 {
    match t {
        Tree::Leaf(v) => *v,
        Tree::Node(m, _, _) => *m,
    }
}

fn query(t: &Tree, lo: usize, hi: usize, l: usize, r: usize) -> i32 {
    if r < lo || hi < l {
        return i32::MAX;
    }
    if l <= lo && hi <= r {
        return min_of(t);
    }
    match t {
        Tree::Leaf(v) => *v,
        Tree::Node(_, left, right) => {
            let mid = (lo + hi) / 2;
            query(left, lo, mid, l, r).min(query(right, mid, hi, l, r))
        }
    }
}

fn main() {
    let a = [9, 1, 0, 3, 9, 4];
    let tree = build(&a);
    println!("{}", query(&tree, 0, a.len(), 3, 6));
}

セグメント木(Boxで子を所有する再帰的な木)で区間[l, r)の最小値を求めるつもりのqueryです。入力はa = [9, 1, 0, 3, 9, 4]・query(&tree, 0, a.len(), 3, 6)(a[3..6] = [3, 9, 4]の最小値)。いまの出力は0ですが、本来の出力は3です。何が問題で、どう直せばよいでしょうか?

Answer

ノードが担当する半開区間[lo, hi)とクエリの半開区間[l, r)が「重なりなし」と判定する条件がr < lo || hi < lになっていますが、半開区間どうしでは、ちょうどhi == lまたはr == loのとき(区間が隣接しているだけで実際には重なっていない)も「重なりなし」として扱わなければなりません。ここでは<を使っているため、この隣接するだけのケースを「重なりあり」と誤判定してしまい、本来なら早期に打ち切るべき再帰をさらに下まで降りてしまいます。その結果、query(&tree, 0, 6, 3, 6)を評価する過程で、区間[0, 3)を担当するノードの中をたどっていき、クエリ範囲の外にある添字2(値0)の葉にまで達して、その値を答えに取り込んでしまいます。範囲外の0が範囲内の本来の最小値3より小さいため、最終的な答えが3ではなく0になります。直し方は、「重なりなし」の判定を<=に変えるだけです:

if r <= lo || hi <= l {
    return i32::MAX;
}