セグメント木を育てる 1

2020年8月31日 23:22

ぬるからです。
青になるために、セグメント木(SegmentTree)なるものの習得が必須だと感じました。
少し勉強したり、ライブラリとして作ったので纏めてみます。

・例題

AOJ:Range Minimum Query (RMQ)
セグメント木のお手本のような問題です。
単純に考えれば、updateにO(1)、findにO(N)かかります。
クオリが全てfindだった場合、O(QN)となるので、O=N=10^5が最大値であるこの問題ではTLEとなります。

・前にnoteに書いたBITに似てる

https://algo-logic.info/segment-tree/
この辺りのサイトが分かりやすかったです。

この考え、前に見たことあるなぁと思っていたのですが
https://note.com/nullkara/n/n35a61d04c3a8
ABC174 Fを解く際に用いた、BITに似ています。
というのも、BITはセグメント木を簡略化し、簡単かつ高速化されたデータ構造です。(ただ、セグ木より制限は多くなっています。)

なので、根本的な考え方は同じです。

・RMQが解けるセグ木を書く

考え方としてはマージソートに近いものを感じました。
アルゴリズムでは、こう二分割して分けて、小さい範囲で考えながら広げていくと早くなる傾向があります。

EX.5 7 8 9 3 2 6 7
　という数列があった場合、これを要素1になるまで二分割します。
　→(5 7 8 9)(3 2 6 7)
　→((5 7)(8 9))((3 2)(6 7))
　→(((5)(7))((8)(9)))(((3)(2))((6)(7)))
　分割後の数列に対して、それぞれの分割後のminを取ります。
　→min(min(min((5)(7))=5,min((8)(9))=8)=5,min(min((3)(2))=2,min((6)(7))=6)=2)=2
　こうすることの何が嬉しかというと、仮に3番目の8が1になったとします。その時の最小値の更新は
　　min(min(min((5)(7))=5,min((1)(9))=8)=5,min(min((3)(2))=2,min((6)(7))=6)=2)=2
　→min(min(min((5)(7))=5,min((1)(9))=1)=5,min(min((3)(2))=2,min((6)(7))=6)=2)=2
　→min(min(min((5)(7))=5,min((1)(9))=1)=1,min(min((3)(2))=2,min((6)(7))=6)=2)=2
　→→min(min(min((5)(7))=5,min((1)(9))=1)=1,min(min((3)(2))=2,min((6)(7))=6)=2)=1
　となり、O(N) かかる最小値の更新がたった4回≒logNで終わります。
　また、全区間の最小値だけでなく、例えば[4,7]区間の最小値が見たい場合、
　min([4,4]=(9),[5,6]=min((3)(2))=2,[7,7]=(6))=2
　と、区間ごとにまとまった値を利用することで、O(N)見なくても、O(logN)見るだけで取得できてしまいます。

　これが、セグ木のRMQです。

・実装

蟻本等をベースにはしますが、あくまで自分で育てるセグ木なので極力見ずに書いていきます。
　※なので、バグとか、遅い処理とかあるかもしれません。コピペするなら、他サイトのを使うかアリ本買って写経してください。

//0-index
vector<int> seqv;
int seqv_n;
void seg_init(int N,int a){
   seqv.clear();
   int n=1;
   while(n<N) n*=2;
   seqv_n=n-1;
   n*=2;
   n=n-1;
   for(int i=0;i<n;i++){
       seqv.push_back(a);
   }
}
void seg_update(int n,int a){
   int k=n+seqv_n;
   seqv[k]=a;
   while(k>0){
       k=(k-1)/2;
       seqv[k]=min(seqv[k*2+1],seqv[k*2+2]);
   }
}

int seg_find(int x,int y){
   struct segF{
       static int segfind(int x,int y,int k,int l,int r){
           //cout<<x<<","<<y<<","<<k<<","<<l<<","<<r<<endl;
           if(r<x||l>y) return LLONG_MAX;
           if(l>=x&&r<=y) return seqv[k];
           else{
               int segl=segfind(x,y,k*2+1,l,(l+r)/2);
               int segr=segfind(x,y,k*2+2,(l+r)/2+1,r);
               return min(segl,segr);
           }
       }
   };
   return segF::segfind(x,y,0,0,seqv_n);
}
void seg_debug(){
   cout<<"---------seg_debug------n="<<seqv_n<<endl;
   int k=1;
   for(int i=0;i<(seqv_n+1)*2-1;i++){
       if(k==i) {
           cout<<endl;
           k=k*2+1;
       }
       cout<<seqv[i]<<" ";
   }
   cout<<endl<<"------------------------------"<<endl;
}

・seg_init
　セグ木をaで初期化します。
　この際、実装を簡略化するために完全二分木として作成します。
　2nサイズの木を作るため、O(2N)=O(N)です。
・seg_update
　seqv_nには一番若番の葉の数字が入っているため、そこに更新する個所のnを足せば、更新する個所の葉が導き出せます。
　あとは/2で上に上がりながら、min値を更新していきます。
　実装を見ての通り、割る2ずつしていくためO(logN)です。
・seg_find
　一番上の範囲から初めて、どんどん下に降りていきます。
　見ている範囲が、調べたい範囲内である場合は、そこの値を返します。
　見ている範囲が、調べたい範囲と全く交わっていない場合、そこは関係ない場所なのでLLONG_MAX(後でminを取るため、影響が出ない大きな数字)を返します。
　O(2N)かかりそうですが、葉に行く前にLLONG_MAXか、範囲内になった領域の数字を返すため、計算量はO(logN)に収まります(らしいです)。
・seg_debug
　二分木の形で、中身を出力する関数です。
　デバッグ用に。

例題は上記のセグ木を使い

signed main(){
   int n,q;
   cin>>n>>q;
   seg_init(n,pow(2,31)-1);
   for(int i=0;i<q;i++){
       int c,x,y;
       cin>>c>>x>>y;
       if(c==0){
           seg_update(x,y);
       }
       else{
           cout<<seg_find(x,y)<<endl;
       }
       //seg_debug();
   }
}

とするだけで、解けてしまいます。
seg_updateで値と最小値の更新、seg_findで区間の最小値を算出します。
計算量は、updateもfindもO(logN)なので、O(QlogN)になります。
O=N=10^5なので、高く見てlogN≒20としても、QlogN=2*10^6です。余裕で間に合いますね。

・応用

ABC125C:GCD on Blackboard
この問題もセグ木で殴れます。

この問題、言い換えると『数列からある一つの数字を取り除いた場合、残った数字の最大公約数の最大は幾らになるか』と言えます。(一つは好きな数字に変えられるので、変えてない数字の最大公約数と同じ数字に変えることで最大化できるため)
区間に直して言い換えると、『kの数字を変える場合、区間(0,k-1)と区間(k+1,N-1)の最大公約数の最大は幾らか』となります。

先ほどの最小のセグ木をgcd用にチェンジ

void seg_update(int n,int a){
   int k=n+seqv_n;
   seqv[k]=a;
   while(k>0){
       k=(k-1)/2;
       if(seqv[k*2+1]==LLONG_MAX) seqv[k]=seqv[k*2+2];
       else if(seqv[k*2+2]==LLONG_MAX) seqv[k]=seqv[k*2+1];
       else seqv[k]=gcd(seqv[k*2+1],seqv[k*2+2]);
   }
}

int seg_find(int x,int y){
   struct segF{
       static int segfind(int x,int y,int k,int l,int r){
           //cout<<x<<","<<y<<","<<k<<","<<l<<","<<r<<endl;
           if(r<x||l>y) return LLONG_MAX;
           if(l>=x&&r<=y) return seqv[k];
           else{
               int segl=segfind(x,y,k*2+1,l,(l+r)/2);
               int segr=segfind(x,y,k*2+2,(l+r)/2+1,r);
               if(segl==LLONG_MAX) return segr;
               if(segr==LLONG_MAX) return segl;
               return gcd(segl,segr);
           }
       }
   };
   return segF::segfind(x,y,0,0,seqv_n);
}

minだった部分をgcdに変えればよいです。
これを用いて、

signed main(){
   int n;
   cin>>n;
   seg_init(n,LLONG_MAX);
   for(int i=0;i<n;i++){
       int A;
       cin>>A;
       seg_update(i,A);
   }
   int ans=seg_find(0,n-1);
   for(int i=0;i<n;i++){
       int a=seg_find(i,i);
       seg_update(i,LLONG_MAX);
       ans=max(ans,seg_find(0,n-1));
       seg_update(i,a);
   }
   cout<<ans<<endl;
}

値を変える部分=gcdを求めない部分を、LLONG_MAXにして、全区間のgcdを求めます。
gcd用に変えたfindやupdateを見ればわかると思いますが、LLONG_MAXの場合はgcdの計算から省くようにしているため、[k,k]区間はgcdの計算から省かれ、[0,k-1]と[k+1,n]区間のgcdが求まります。

このように最小以外にも少し変えるだけで、区間の何たらが求められるようになります。

・終わりに

遅延評価セグメント木とか、高速化とか、
もっと深く知れば、区間系の問題をセグ木で殴って解決できるようになるとかどうとか？
私も早く、セグ木が想定解でない問題を無理やりセグ木で殴って解きたいものです。

この記事が気に入ったらサポートをしてみませんか？