遅延セグメント木
まずセグ木とは
セグメント木(Segment Tree)の略称です。
モノイドを満たす長さNの配列に対し、以下の操作ができます。
- i番目の要素の変更
- i番目からj番目までの要素の最小値、最大値、総積などを求める
これらを O(log N) で処理できるのが特徴です。
初期化は O(N) です。
派閥がありそうですが、私は葉の数を2の累乗にして完全二分木にします。
また、区間は半開区間 [l,r) で表記します。
例えば、n=8のa={4,3,3,8,5,7,5,2}が入力されたとすると最小値を求めるセグ木は以下のようになりますね。
葉にaをそのままセットして、親には子のうち小さいほうの値をセットしていきます。
ここでa[1]=1という一点更新があったとします。すると、以下のように更新されますね。
上の画像のように特定の葉ノードに対し更新処理をする際、その葉ノードから根に向かって更新をしていうことになります。完全二分木の高さはlogNなので、一点更新の計算量はO(logN)となるわけです。
しかし、ここで問題があります。
もし一点ではなく、aのl~rまでの区間を全て1に更新するという処理がきたらどうなるでしょうか。
logNの更新処理をr-l回行うことになり、最悪の場合の時間計算量はO(NlogN)となってしまいます。
ぱっと見高速に見えますが、この更新クエリが複数回飛んでくると間に合わなくなったりします。
よって、この問題に適応するべくセグ木を進化させる必要があります！
この「区間更新をまとめて処理したい」という要求に応えるのが遅延セグメント木です。
遅延セグ木とは
セグ木では一点のみの更新しか行えませんが、遅延評価セグメント木は区間更新、区間クエリを高速に行えます。
遅延セグ木を用いると、このクエリを O(logN) で実行できます。
特性
遅延セグ木は、必要になるまで更新を子ノードに伝播させないことで計算量を抑えます。
具体的には配列を二つ持ち、それぞれに担当を分けさせます。
- seg：セグ木で作るseg配列と同じで実際の値を持つ
- lazy：遅延評価を貯めておくための配列
実装
問題文があるとやりやすいので、今回はAIZU ONLINE JUDGEの以下の問題(RMQ、RUQ)を解くことにします。
問題文を見た瞬間に遅延セグ木を連想するようなザ・典型ですが、個人的には最大値を求める問題の方が最初は考えやすいのかなと思っています。
問題ページはこちら
Step1
まずはmain部分を作成しましょう。
最終的に答えを出力する必要があるので、 ans を宣言しておきます。
入力を受け取るところまでです。
int main(){
int n,q;
cin>>n>>q;
vector<ll> ans;
for(int i=0;i<q;i++){
int type;
cin>>type;
if(type==0){
int s,t,x;
cin>>s>>t>>x;
}
else{
int s,t;
cin>>s>>t;
}
}
for(auto tmp:ans) cout<<tmp<<endl;
}
type=0の時はupdate、type=1の時はfindです。
Step2
さて、まずは構造体を作り、セグ木を作成するところまで進めます。これはセグ木が理解できていれば分かる範囲なので説明はしません。また、これも派閥ですがinit関数を用意します。
lazyの初期値ですが、遅延情報が溜まっているか区別する必要があるため入力されない値を入れる必要があります。今回は負の値が入力されないため-1 にでもしておきます(これにより、lazy[k]=-1のときに遅延情報がないことがわかるようになった)。
const ll INF=(1LL<<31)-1;
struct LazySegTree{
int n;
vector<ll> seg,lazy;
void init(int sz){
n=1;
while(n<sz) n*=2;
seg.assign(n*2,INF);
lazy.assign(n*2,-1);
}
};
int main(){
int n,q;
cin>>n>>q;
LazySegTree seg;
seg.init(n);
vector<ll> ans;
for(int i=0;i<q;i++){
int type;
cin>>type;
if(type==0){
int s,t,x;
cin>>s>>t>>x;
}
else{
int s,t;
cin>>s>>t;
}
}
for(auto tmp:ans) cout<<tmp<<endl;
}
Step3
更新処理(update)を書いていきます。
例えば、先ほどの配列a={4,3,3,8,5,7,5,2}をセットした時のseg、lazy配列の初期状態を図にすると以下のようになります。
ここで [9,13) に対して値を5にするという更新処理が飛んできたとします。
セグ木同様、なるべく上位(根に近い)のノードで覆うと、以下のように{9,5,12}が選ばれますね。
途中ですが、更新処理 / クエリ処理で頻繁に登場する上記のような更新に関係のある葉ノードを完全に被覆するようなノード(今回なら{9,5,12})のことを 大きな範囲 と呼ぶことにします。(このノードたちの呼び方みんな困ってる気がする)
遅延セグ木では、区間更新があった際にすぐseg配列の中身を変更するのではなく、lazy配列のみを更新します。
lazyの各ノードはそのノード以下に伝播させたい情報を持ちます。
今回であれば、値を5にするという情報を持ちます。
seg配列の中身は何も変化していませんね。
ここで、[10,15)の最小値を教えて欲しいと言われたとしましょう。
セグ木がかければ分かることですが、区間 [l,r) に対する更新では、根から葉に向かって各ノードを見た時に、次の3ケースのどれかに該当します。
-
今見ているノードが、
[l,r)に完全に含まれる- seg[k]を
returnする
- seg[k]を
-
今見ているノードが、
[l,r)に部分的に含まれる- 1、3のどちらかに該当するまで子に再起的に移動
- その際lazy[k]に遅延情報が溜まっていれば子に伝播させる
-
今見ているノードが、
[l,r)に全く含まれない- これ以上子を見る必要がないため
return
- これ以上子を見る必要がないため
kは今見ているノードのindexです
今回の例を見ながら順を追ってみていきましょう。
根から葉に向かって再起的に操作します。
根が持つ範囲は[8,16)ですね。今更新したい区間は[10,15)なので2に該当しますので、子に移ります。
index=2のノードが持つ範囲は[8,12)ですので、これも2に該当します。
さらに子に移りますがindex=4が持つ範囲は[8,10)なので、これは3となります。よって、これ以上子を見る必要がなくなったため、index=5へ移ります。
ここで、初めてlazy[k]の値が-1ではない場面に遭遇しました。
以下の処理をevalという関数にまとめます
このevalが核となる部分なので、この後説明します。
遅延セグ木は、必要なときまで更新処理を止めておくという特性があると話しましたが、今こそがその必要なときなのです。つまり、ノードを移動しながら
lazy配列を参照し、遅延情報を持っていれば(今回の場合lazy[k]!=-1なら)、その情報をseg[k]と子ノード(=lazy[k*2],lazy[k*2+1])へと伝播させます。
index=5の持つ範囲は[10,12)なので1に該当します。よって以下のように遅延情報を伝播させた後のindex=5の値、つまり5を返します。
また、遅延情報を伝播し終わったlazy[k]は再度-1に戻しておきましょう。
evalの役割
eval の役割を一言でいうと、「保留していた更新内容を、必要になった瞬間にそのノードと子ノードに反映させる」 というものです。
具体的には、以下の2つの処理をセットで行っています。
-
自分自身への反映
- lazy[k] に値が入っている場合、それは「まだこのノードの seg[k]（実際の値）を更新していない」という印です。まずは lazy の値を seg に書き込み、最新の状態にします。
-
子ノードへの「伝言」
- 自分が最新になったら、次は自分の子供たち（下の階層）にも同じ更新を伝える必要があります。ただし、ここで一番下まで一気に更新すると時間がかかるため、すぐ下の子供の lazy 配列にメモを残すだけにとどめます。
なぜ各関数の最初で eval を呼ぶのか？
update や query 関数の中で、ノードに立ち寄った瞬間にまず eval を呼び出しています。これには 「古い情報のまま計算してしまうのを防ぐ」 という意味があります。
更新（update）のとき：古い情報の上に新しい情報を重ねると計算が狂うため、一度最新にしてから上書きする。
取得（query）のとき： 正しい（最新の）値を見ないと、間違った最小値を返してしまう。
このように、「使う直前に更新する」という仕組みによって、無駄な計算を省きつつ正確な値を保っているのです。
また、木の各高さについて1回の更新あたり子ノードに移動する回数は一番左右の2ノードのみであるため高々2回となり、O(log N) が保証されます。
定数倍のオーバーヘッドは存在します。
struct LazySegTree{
int n;
vector<ll> seg,lazy;
void init(int sz){
n=1;
while(n<sz) n*=2;
seg.assign(n*2,INF);
lazy.assign(n*2,-1);
}
void eval(int k,int l,int r){
if(lazy[k]!=-1){
seg[k]=lazy[k];
if(r-l>1){
lazy[k*2]=lazy[k];
lazy[k*2+1]=lazy[k];
}
lazy[k]=-1;
}
}
void update(int a,int b,ll x,int k=1,int l=0,int r=-1){
if(r==-1) r=n;
eval(k,l,r);
if(b<=l||r<=a) return;
if(a<=l&&r<=b){
lazy[k]=x;
eval(k,l,r);
}
else{
int m=(l+r)/2;
update(a,b,x,k*2,l,m);
update(a,b,x,k*2+1,m,r);
seg[k]=min(seg[k*2],seg[k*2+1]);
}
}
};
int main(){
int n,q;
cin>>n>>q;
LazySegTree seg;
seg.init(n);
vector<ll> ans;
for(int i=0;i<q;i++){
int type;
cin>>type;
if(type==0){
int s,t,x;
cin>>s>>t>>x;
seg.update(s,t+1,x);
}
else{
int s,t;
cin>>s>>t;
}
}
for(auto tmp:ans) cout<<tmp<<endl;
}
Step4
クエリ処理(query)を書いていきます。
queryと書いていますが、これが問題文で言うとこのfindです。
こちらはあまり解説するポイントがありません。
大きな範囲 のノードを見て、値を返すだけです。
#include <iostream>
typedef long long ll;
using namespace std;
const ll INF=(1LL<<31)-1;
struct LazySegTree{
int n;
vector<ll> seg,lazy;
void init(int sz){
n=1;
while(n<sz) n*=2;
seg.assign(n*2,INF);
lazy.assign(n*2,-1);
}
void eval(int k,int l,int r){
if(lazy[k]!=-1){
seg[k]=lazy[k];
if(r-l>1){
lazy[k*2]=lazy[k];
lazy[k*2+1]=lazy[k];
}
lazy[k]=-1;
}
}
void update(int a,int b,ll x,int k=1,int l=0,int r=-1){
if(r==-1) r=n;
eval(k,l,r);
if(b<=l||r<=a) return;
if(a<=l&&r<=b){
lazy[k]=x;
eval(k,l,r);
}
else{
int m=(l+r)/2;
update(a,b,x,k*2,l,m);
update(a,b,x,k*2+1,m,r);
seg[k]=min(seg[k*2],seg[k*2+1]);
}
}
ll query(int a,int b,int k=1,int l=0,int r=-1){
if(r==-1) r=n;
eval(k,l,r);
if(b<=l||r<=a) return INF;
if(a<=l&&r<=b) return seg[k];
int m=(l+r)/2;
return min(query(a,b,k*2,l,m),query(a,b,k*2+1,m,r));
}
};
int main(){
int n,q;
cin>>n>>q;
LazySegTree seg;
seg.init(n);
vector<ll> ans;
for(int i=0;i<q;i++){
int type;
cin>>type;
if(type==0){
int s,t,x;
cin>>s>>t>>x;
seg.update(s,t+1,x);
}
else{
int s,t;
cin>>s>>t;
ans.push_back(seg.query(s,t+1));
}
}
for(auto tmp:ans) cout<<tmp<<endl;
}
ということで完成です！！
最後に
個人的にlazyにアクセスするタイミングがなんとなくで書いていてサンプルが通らなければ書き換えてみたいなことやっていたので、今回で整理できてよかったです。
なるべく間違いのないよう使用している言葉などにも気をつけましたが、変な箇所があれば指摘頂きたいです。
メリークリスマス！！！