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;
}