Namaran

Code daily. Without assist.

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要素ずつ切り出しても正しく動きます)。