2026-09-23
segtree_build.rs
enum Tree {
Leaf(i32),
Node(i32, Box<Tree>, Box<Tree>),
}
fn min_of(t: &Tree) -> i32 {
match t {
Tree::Leaf(v) => *v,
Tree::Node(m, _, _) => *m,
}
}
fn build(a: &[i32]) -> Tree {
}
Treeは区間最小値を管理する二分木で、葉(Leaf)には1つの値を、内部ノード(Node)にはその部分木全体の最小値と、左右の子(それぞれBoxで所有)を持ちます。空でないスライスaから、左右にほぼ半分ずつ分割してこの木を組み立てるbuildを書いてください。要素数が1のときはLeafを1つ返します。min_of(&build(&[4])) → 4(境界: 要素数1)、min_of(&build(&[4, 1])) → 1、min_of(&build(&[4, 1, 7, 2])) → 1
Reference
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))
}
}
要素数が1なら、それ以上分割せずにLeafを1つ返します。そうでなければa.len() / 2で左右にほぼ半分ずつ分け、それぞれを再帰的にbuildしてから、両者の最小値の小さい方をNodeが持つ最小値として持たせます。Box::newで子を包むことで、Nodeは左右の子の所有権をそのまま引き継ぎます。これは参考実装であり、唯一の正解ではありません(分割位置は必ずしも中央でなくてもよく、例えば1要素ずつ切り出しても正しく動きます)。