2026-09-23
segtree_box.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 update(t: &mut Tree, len: usize, i: usize, v: i32) {
match t {
Tree::Leaf(x) => *x = v,
Tree::Node(m, left, right) => {
let mid = len / 2;
if i < mid {
update(left, mid, i, v);
} else {
update(right, len - mid, i - mid, v);
}
*m = min_of(left).min(min_of(right));
}
}
}
fn main() {
let a = [5, 2, 8, 1, 9];
let mut tree = build(&a);
println!("{}", min_of(&tree));
update(&mut tree, a.len(), 3, 10);
println!("{}", min_of(&tree));
}
このプログラムは何を出力するでしょうか?
Answer
1と2(2行)です。Treeは区間最小値を管理する二分木を、ノードへの生ポインタではなくBoxで子を所有する形で表現したもので、親から子への所有権と子から親への参照を同時に持つ木を素直には書けないRustでは、この「親が子をBoxで所有する」形が典型的な作り方になります。buildは配列をほぼ半分ずつに割りながら再帰的にLeafとNodeを組み立て、各Nodeには自分の部分木全体の最小値をあらかじめ計算して持たせます。a = [5, 2, 8, 1, 9]全体の最小値は1なので、1回目のprintln!は1を出力します。続くupdate(&mut tree, a.len(), 3, 10)は添字3(値1)を10に書き換えます。updateは&mut Treeを辿りながら目的の葉をLeaf側の分岐で直接更新し、再帰から戻る途中のNode側の分岐で*m = min_of(left).min(min_of(right));によりその部分木の最小値を持ち直します——所有権が親から子への一方向であることと、&mutによる排他的な借用のおかげで、木を下りながら書き換え、上りながら値を集約し直す、という操作が安全に書けます。更新後の配列は[5, 2, 8, 10, 9]なので最小値は2になり、2回目のprintln!は2を出力します。