第x回プロコン分科会(seg木)
seg木
このへんから高速化とかそういう技術が必要になってきます
logNは定数。(要出典)
一般的なの
RMQ。ある区間内の最大(最小)値、一か所の変更ができる。
int N; int seg[400005]; void init(){ N=1; while(N<=n)N*=2; rep(i,N)seg[i+N]=-inf; rep(i,n)seg[i+N]=初期値[i]; ireg(i,1,N-1)seg[i]=max(seg[i*2],seg[i*2+1]); } int get(int l,int r,int a,int b,int k){ //今、区間[l,r)(ちょうどk番目のノード)を見ていて、 //クエリは[a,b)内のmaxを返してくれ、というやつ。 if(r<=a || b<=l)return -inf; //全くかぶってない if(a<=l && r<=b)return seg[k]; //☆ return max( get(l,(l+r)/2,a,b,k*2), get((l+r)/2,r,a,b,k*2+1)); //わける } int get_max(int a,int b){ //外部からはこのようにgetを呼び出す return get(0,N,a,b,1); } void update(int p,int a){ //位置aを値pにする a+=N; seg[a]=p; a/=2; while(a>0){ seg[a]=max(seg[a*2],seg[a*2+1]); a/=2; } }
注意)
segの長さは、n*4くらい取っておくこと。
(Nがn*2くらいまでなって、segは2*N要素くらいいる)
半開区間です。
で、一回の呼び出しに対して、
updateはlog(N)回くらいwhile文が回る。
get の呼び出し回数が増えるのは、☆のところだが、
☆が呼び出されるのは、[l,r)と[a,b)が交差するとき。
で、それぞれの端点a,bについて、交差している区間はたかだかlog(N)個なので、
全部でだいたい4*log(N)回くらいgetが呼び出される。
ので、クエリに対してO(log(N))で答えられる、やったね、という話。
派生
各ノードに対してvectorとかsegtreeとかを持たせる話もある。
(2次元平面に対してある区域内の点の個数を求める、とか)
starry sky tree
ある区間内のmin、ある区間への加算、みたいなクエリに対して答えろ、という問題がある。
(seg木を二つ持てば解けるが同上)
これを解くのがstarry_sky_treeと呼ばれるやつ。
seg木は二分木なわけだが、「根以外のとこでは片方のノードは0」「根から葉までの値の累積和が各地点の値となる」
を満たすように、うまいことseg木を更新してやる。
たとえば、
[3, 1, 4, 1, 5, 9, 2, 6]
は、
[ 1 ] [ 0 ],[ 1 ] [ 0 ],[ 0 ],[ 3 ],[ 0 ] [2],[0],[3],[0],[0],[4],[0],[4]
みたいなのでもつ。
さて、実装ですが、
getは取ってくるだけですが、updateがちと面倒です。(ポロロッカさせる必要がある)
// validated at http://codeforces.com/problemset/problem/52/C int N; lli seg[800005]; void init(){ N=1; while(N<=n)N*=2; rep(i,n)seg[i+N]=dat[i]; reg(i,n,N-1)seg[i+N]=inf; ireg(i,1,N-1){ seg[i]=min(seg[i*2],seg[i*2+1]); seg[i*2]-=seg[i]; seg[i*2+1]-=seg[i]; } } lli get(int l,int r,int a,int b,int k){ if(r<=a || b<=l)return inf; if(a<=l && r<=b)return seg[k]; return seg[k] + min( //いままでの累積+子の最小値 get(l,(l+r)/2,a,b,k*2), get((l+r)/2,r,a,b,k*2+1)); //[l,r)の区間の部分木をちっちゃなseg木とみなしたときに //ちゃんと最小値が返っているようにする。 } lli get_min(int a,int b){ //外部からはこのようにgetを呼び出す return get(0,N,a,b,1); } void update(int l,int r,int a,int b,int k,lli p){ //区間[a,b)にpを加える if(r<=a || b<=l)return; if(a<=l && r<=b){ seg[k] += p; return; } update(l,(l+r)/2,a,b,k*2,p); update((l+r)/2,r,a,b,k*2+1,p); //この時点で、左右の子より下の部分は全て正常化されている筈。 //で、現状、自分を含む子ノードの部分は、適当なa,b,cを用いて(aが今のノード) //[ a ] //[ b ],[ c ] //となってるはず。で、 //「左ルートの累積がa+b,右ルートの累積がa+c」 // である状態を保ちつつ、 //「どちらかの子ノードの値が0,もう片方は正」 // であるようにするには、これを //[ a + min(b,c) ] //[ b-min(b,c) ],[ c-min(b,c) ] //としてやればよい。 lli por = min(seg[k*2],seg[k*2+1]); seg[k]+=por; seg[k*2]-=por; seg[k*2+1]-=por; } void update_x(int a,int b,lli p){ //外部からはこのようにupdateを呼び出す update(0,N,a,b,1,p); }
seg木ではない
BIT木(Fenwick Tree)
クエリがmaxではなくsumとかのとき、[1,x)と[1,y)から[x,y)が求まるので、持つノードの数が少なくできる。
BIT木に再帰的にBIT木を持たせる、とかいう話もある。
bit演算を用いると遷移が簡単に書けるよ、というもの。
実装は蟻本を見てください。
平方分割
seg木と似たような考え方として、「平方分割」というやつがある。
(僕はseg木の劣化版だと思っていたが、seg木でできない問題も解けたりするのでなかなか)
平衡二分探索木
http://www.slideshare.net/iwiwi/2-12188757
これとか。
seg木にはできないことをやってのける。
勉強になるの
http://kagamiz.hatenablog.com/entry/2012/12/18/220849
とか、
http://www.slideshare.net/iwiwi/ss-3578491
とか、
http://d.hatena.ne.jp/kyuridenamida/20121114/1352835261
とか、
http://d.hatena.ne.jp/DEGwer/20131211/1386757368
とか、
http://hogloid.hatenablog.com/entry/20121227/1356608982
とか、
http://d.hatena.ne.jp/tozangezan/20111111/1320993464
とか。