Namaran

Code daily. Without assist.

2026-09-30

min_tree.rs

fn build(a: &[i32]) -> Vec<Option<i32>> {
    let n = a.len().next_power_of_two();
    let mut t = vec![None; 2 * n];
    for (i, &x) in a.iter().enumerate() {
        t[n + i] = Some(x);
    }
    for i in (1..n).rev() {
        t[i] = t[2 * i].min(t[2 * i + 1]);
    }
    t
}

fn main() {
    let t = build(&[4, 2, 7]);
    println!("{:?}", t[1]);
}

build は、配列の区間の最小値を求めるセグメント木を作るつもりの関数です。葉の数を2のべきに切り上げ、要素のない葉は None にしています。main のとおり [4, 2, 7] から作ると、根の t[1] は本来 Some(2) になるはずですが、いまは None と出力します。

Answer

Wrong

for i in (1..n).rev() {
    t[i] = t[2 * i].min(t[2 * i + 1]);
}

Option の順序では、None はどの Some よりも小さいと決まっています。要素が3つなので葉は4枚に切り上げられ、最後の葉の t[7] が None になります。t[3] は Some(7).min(None) で None になり、根の t[1] も Some(2).min(None) で None になります。

None を「値がない」という意味で置いても、min はそれを一番小さい値として選びます。どの値と min を取っても相手をそのまま返す値を min の単位元と呼び、それになれるのはどの値よりも大きいものだけです。

Right

for i in (1..n).rev() {
    t[i] = t[2 * i].into_iter().chain(t[2 * i + 1]).min();
}

Option は、要素を0個か1個持つイテレータとして扱えます。2つの子を chain でつないで Iterator::min を取ると、None の側は要素を出さないので比較に加わらず、両方が None のときだけ結果が None になります1。

  1. Option をやめて、空いた葉を i32::MAX で埋める書き方もよく使われます。i32::MAX はどの i32 と min を取っても相手を返すので、min の単位元になります。