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になります。