2026-09-30
update.rs
fn update(t: &mut [i32], i: usize, v: i32) {
}
t は区間の最小値を求めるセグメント木で、長さは 2n です。t[n + j] が元の配列の j 番目の要素で、1 以上 n 未満の k について t[k] は t[2k] と t[2k + 1] の小さい方です。t[0] は使いません。元の配列の i 番目を v に書き換え、t がこの形を保つようにする update を書いてください。n が 1 なら、書き換えるのは葉の t[1] だけです。出力例は、呼び出したあとの t です。
入力例 1
let mut t = [0, 3, 3, 6, 5, 3, 8, 6]; update(&mut t, 1, 9);
出力例 1
[0, 5, 5, 6, 5, 9, 8, 6]
入力例 2
let mut t = [0, 3, 3, 6, 5, 3, 8, 6]; update(&mut t, 2, 1);
出力例 2
[0, 1, 3, 1, 5, 3, 1, 6]
入力例 3
let mut t = [0, 4]; update(&mut t, 0, 7);
出力例 3
[0, 7]
Reference
fn update(t: &mut [i32], i: usize, v: i32) {
let mut i = i + t.len() / 2;
t[i] = v;
while i > 1 {
i /= 2;
t[i] = t[2 * i].min(t[2 * i + 1]);
}
}
葉 t[n + i] を書き換えたとき、値が変わりうるのはその葉の祖先だけです。n は t.len() / 2 で求まり、節 i の親は i / 2 なので、i を半分にしながら根の t[1] まで上り、各節を2つの子の小さい方で計算し直します。
親を t[i] = t[i].min(v) で直したくなりますが、これは値が小さくなる更新にしか使えません。例1は最小値だった 3 を 9 に上げるので、この書き方では t[1] と t[2] に古い 3 が残ります。子から計算し直せば、上げる更新も下げる更新も同じ形で扱えます。
掲載したのは参考実装で、唯一の正解ではありません。上るたびに i ^ 1 で兄弟の節を求め、t[i].min(t[i ^ 1]) を親に入れる書き方もあります。