Namaran

Code daily. Without assist.

2026-09-30

tree.rs

fn main() {
    let a = [7, 9, 6, 5, 2];
    let n = a.len();
    let mut t = vec![0; 2 * n];
    t[n..].copy_from_slice(&a);
    for i in (1..n).rev() {
        t[i] = t[2 * i].min(t[2 * i + 1]);
    }
    println!("{:?}", &t[1..n]);
}

これは何を出力するでしょうか?

Answer

[2, 2, 6, 2] です。

葉は t[5] から t[9] に並び、t[5 + i] が a[i] です。内部の節 t[i] には、子の t[2 * i] と t[2 * i + 1] の小さい方が、i の大きい順に入ります。

t[4] の子は葉の t[8] と t[9] で、これは a[3] と a[4] なので 2 です。同じく t[3] の子の t[6] と t[7] は a[1] と a[2] で、t[3] は 6 になります。

t[2] の子は t[4] と t[5] ですが、t[5] は内部の節ではなく葉の a[0] です。t[2] が持つのは a[3]、a[4]、a[0] の最小値 2 で、配列の連続した区間には対応しません。根の t[1] は t[2] と t[3] の小さい方の 2 です。

t[2] を左半分 [7, 9, 6]、t[3] を右半分 [5, 2] の最小値と読むと、t[2] を 6、t[3] を 2 と答えたくなります。節をそう読めるのは、n が2のべきのときだけです1。

  1. それでもこの形の木で、区間 [l, r) の最小値は正しく求められます。葉から根へ向かって上る問い合わせは区間の内側に収まる節だけを使うので、t[2] のように端から回り込んだ節には届きません。