2026-09-22
range_min.rs
fn range_min(tree: &[i32], n: usize, mut l: usize, mut r: usize) -> i32 {
}
treeは要素数nの配列に対する区間最小値のセグメント木で、葉がtree[n..2*n]に、内部ノードtree[i](1 <= i < n)には子tree[2*i]・tree[2*i+1]の小さい方が入っています(tree[0]は未使用)。半開区間[l, r)(元の配列の添字基準)の最小値を返すrange_minを書いてください。l == r(空区間)のときはi32::MAXを返します。例えばtree = [i32::MAX, 1, 1, 3, 2, 1, 3, 4, 5, 2, 8, 1, 9, 3, 7, 4](n = 8、元の配列は[5, 2, 8, 1, 9, 3, 7, 4])のとき、range_min(&tree, 8, 0, 8) → 1、range_min(&tree, 8, 4, 8) → 3、range_min(&tree, 8, 3, 3) → i32::MAX(境界: 空区間)
Reference
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]);
l += 1;
}
if r % 2 == 1 {
r -= 1;
res = res.min(tree[r]);
}
l /= 2;
r /= 2;
}
res
}
葉の位置に揃えるためl・rにnを足します。そこから、区間[l, r)を上の階層へ縮めながら、区間の外側にはみ出す葉だけを答えに取り込んでいきます。lが奇数(親から見て右の子)ならそのノード自体が区間に含まれる最大のまとまりなので取り込んで1つ右へ進め、rが奇数(区間の外)なら1つ左の(区間に含まれる)ノードを先に取り込んでから縮めます。最後にl・rをともに2で割って1つ上の階層に上がり、l < rである限り繰り返します。これは参考実装であり、唯一の正解ではありません(木を再帰でたどる書き方もできます)。