競プロ用ライブラリを作る Advent Calendar 2024の14日目です.
LazySegmentTreeって?
SegmentTreeは値の更新は1か所ずつしかできませんでした. そのため, ある区間の要素の値を全部更新, のようなことをしようとすると時間がかかってしまいます.
LazySegmentTreeは良い感じに計算を後回しにすることで区間の要素の値を全部更新, というクエリも高速に行えるようにするデータ構造です.
仕組み
SegmentTreeでやったようにして, 私たちはいくつかの区間の情報を持って
- 指定した区間を情報を持っている区間の組み合わせで表現する
- 指定した要素を含んだ情報を持っている区間を全て挙げる
が対数時間で行えます.
区間更新クエリがあるときもこれを活用しましょう. 情報を持っている区間に更新の情報も持たせます.「この区間の要素を全部こういう風に更新する必要があるけど後回しにしてます」という情報を持つようにします.
// サンプルでは
// - 区間の最小値を答えるクエリ
// - 区間内の値に要素を足すクエリ
// を処理するものを実装します
struct SampleLazySegTree {
// それぞれの区間での最小値
data: Vec<Vec<i32>>,
// 足すのを保留している量
hold: Vec<Vec<i32>>,
}
一点取得
取得したい要素の更新が保留されている可能性があるので, その要素を含む区間の保留を全て処理して保留を無くしてから取得します
impl SampleLazySegTree {
// indexに対応する要素に正しい値が入るように, 保留を処理していく
// 色々なところで使うので, この機能を持つ関数を用意すると便利でしょう
fn update_point(&mut self, index: usize) {
// 上の層から順に更新していく
for i in (0..self.data.len()).rev() {
// i層目でindexに対応する要素を含む区間はindex >> i番目にあります
let j = index >> i;
// index番目に対応する要素が無いこともあるので, チェックしましょう
if j < self.data[i].len() {
continue;
}
// 情報を更新する
self.data[i][j] += self.hold[i][j];
// 下の層があるなら, その層にも更新する必要があるという情報を反映する
if i > 0 {
// 下の層の対応する区間はj*2とj*2+1のところにあります
self.hold[i - 1][j * 2] += self.hold[i][j];
self.hold[i - 1][j * 2 + 1] += self.hold[i][j];
}
// 更新が終わったので, 2重に更新しないように保留がないという情報を入れます
self.hold[i][j] = 0;
}
}
fn get_point(&mut self, index: usize) -> &i32 {
self.update_point(index);
// 更新が終わったので, 正しい値が入っています. これを出力します
&self.data[0][index]
}
}
一点更新
- 保留を処理して正しい値が入っているようにする
- 値を更新する
- 値の更新の影響を受ける区間の情報も更新
の順にするとよいです
impl SampleLazySegTree {
// indexに対応する要素を更新した後, 影響を受ける区間の情報も更新する
// これも複数個所で使うので共通化します
// やることはLazyでないSegmentTreeと同じです
fn update_point(&mut self, index: usize) {
for i in 1..self.data.len() {
let idx = index >> i;
if idx >= self.data[i].len() {
break;
}
self.data[i][idx] = self.data[i - 1][idx * 2] + self.data[i - 1][idx * 2 + 1];
}
}
fn set_point(&mut self, index: usize, val: i32) {
self.resolve_point(index);
self.data[0][index] = val;
self.update_point(index);
}
}
区間取得
SegmentTreeのときと同じようにしたいので, まず, 使う区間の情報の保留を解決したいです. ただ, あまりにも多くの更新が起こると遅いので更新する区間の数は少なくしたいです.
実は半開区間$[l, r)$のクエリのときはself.resolve_point(l)とself.resolve_point(r - 1)を実行すれば使う区間の1つ上の層の情報は全て更新されます.
ということで, 区間を使うときはその区間の保留の情報だけを見れば正しい値になります. これが分かればあとはSegmentTreeと同じようにやるだけです
impl SampleLazySegTree {
// 半開区間[left, right)のクエリ
fn get_range(&mut self, mut left: usize, mut right: usize) -> i32 {
self.resolve_point(left);
self.resolve_point(right - 1);
let mut min = i32::MAX;
// SegmentTreeと同じように計算します
// 区間の情報を得る前に保留を処理するのがポイントです
for i in 0.. {
if left % 2 == 1 {
// 区間の保留を処理する
self.data[i][left] += self.hold[i][left];
if i > 0 {
self.hold[i - 1][left * 2] += self.hold[i][left];
self.hold[i - 1][left * 2 + 1] += self.hold[i][left];
}
self.hold[i][left] = 0;
// 答えの更新
if self.data[i][left] < min {
min = self.data[i][left]
}
left += 1;
}
if right % 2 == 1 {
right -= 1;
// 区間の保留を処理する
self.data[i][right] += self.hold[i][right];
if i > 0 {
self.hold[i - 1][right * 2] += self.hold[i][right];
self.hold[i - 1][right * 2 + 1] += self.hold[i][right];
}
self.hold[i][right] = 0;
// 答えの更新
if self.data[i][right] < min {
min = self.data[i][right]
}
}
if left == right {
return min;
}
left /= 2;
right /= 2;
}
unreachable!();
}
}
区間更新
とりあえず保留があるとめんどくさいので, 更新する区間の保留を解消します. 区間取得と同じようにすればいいです
で, 区間取得と同じように必要最低限な区間を選んで保留の情報を書き換えます.
その上の層の区間は正しい情報を持たせたいので, 最初にself.resolve_point(left)とself.resolve_point(right - 1)をしたのと同じノリでself.update_point(left)とself.update_point(right - 1)をします.
が, このupdate_pointは更新する区間に保留が無いときしか上手く動かない設計なので, resolve_pointしてから動かすようにします.
(resolve_pointは区間の情報が正しくないときに正しい区間の値にしてくれませんが, その後正しい区間の値に設定する処理を行うので大丈夫です)
impl SampleLazySegTree {
// 半開区間[left, right)の範囲にvalを加えるクエリ
fn set_range(&mut self, mut left: usize, mut right: usize, val: i32) {
self.resolve_point(left);
self.resolve_point(right - 1);
// 区間の最小値を得たときと同じようなフローで組み合わせの区間を得ます
for i in 0.. {
if left % 2 == 1 {
self.hold[i][left] += val;
left += 1;
}
if right % 2 == 1 {
right -= 1;
self.hold[i][left] += val;
}
if left == right {
break;
}
left /= 2;
right /= 2;
}
// 工夫すると無駄な処理を減らせますが, オーダーは変わらないので気にせずいきましょう
self.resolve_point(left);
self.resolve_point(right - 1);
self.update_point(left);
self.update_point(right - 1);
}
}
実装
実装は大変ですが, 便利なので頑張って実装しましょう
まとめ
いかがでしたか?
明日はもっと重実装なものを実装します