セグメント木を育てる 2

・問題を区間に言い換える

ARC033-C_データ構造
集合Sに数字が追加されていくので、下からX番目の数字が何かを答える問題です。
set等で解けそうな感じですが、一番大きいor一番小さいはO(1)で分かるのですが、下からX番目は辿っていくしかなくO(N)かかっちゃいます。

・数字Xが下から何番目かを記録する配列を持つ。
　EX.5 8 3 9 2と数字が追加されるとします。
　0 0 0 0 0 0 0 0 0 という要素9個の配列を用意し、ここに1～9の値が下から何番目かを記録していきます。
　5 → 0 0 0 0 1 1 1 1 1
　8 → 0 0 0 0 1 1 1 2 2
　3 → 0 0 1 1 2 2 2 3 3
　9 → 0 0 1 1 2 2 2 3 4
　2 → 0 1 2 2 3 3 3 4 5
　例えば、5の場合は、5番目の要素3が答えになります。
　実際に5より小さい数字は2と3なため、5は3番目に小さいです。
　こうすることで嬉しいことは、できた配列が昇順になるため、二分探索(C++でいうlower_bound)でX番目に小さい数字が求められることです。
　更に更新された値を見てみると、まるで累積和のような更新の仕方になっています。区間で言い換えると、数字Aが追加された場合、区間(A,N)が1増える。と言えます。

・セグ木を累積和用に改造
minをプラスに変えると、累積和が求められるようになります。
範囲外はLLONG_MAXではなく0を返すようにしましょう(プラスに変えたため、LLONG_MAXのままだと、計算に影響が出ます。0の場合、0を足しても答えは変わらないため影響が出ません。)

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 0;
          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 segl+segr;
          }
      }
  };
  return segF::segfind(x,y,0,0,seqv_n);
}

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

・上記のセグ木を使って実装
上記のセグ木を使い、二分探索で答えを探すコードを実装します。

signed main(){
   int Q;
   cin>>Q;
   seg_init(200000,0);
   for(int i=0;i<Q;i++){
       int T,X;
       cin>>T>>X;
       if(T==1){
           seg_update(X,1);
       }
       else{
           int l=0;
           int r=200000;
           while(1){
               int mid=(l+r)/2;
               int n=seg_find(0,mid);
               //cout<<mid<<","<<n<<endl;
               if(n>=X){
                   if(r==mid) break;
                   r=mid;
               }
               else{
                   if(l==mid) break;
                   l=mid;
               }
           }
           cout<<r<<endl;
           seg_update(r,0);
       }
   }
}

区間じゃなさそうな問題を区間に言い換えることにより、セグ木を使ってACすることができました。

・BIT

上記の実装のfindを見てほしいのですが、

int n=seg_find(0,mid);

と、実は0から始まる区間のfindしか行っていません。
サイズ8のセグ木に対して0から始まる区間のfindを考えた場合
区間は(0,7),(0,3),(0,1),(0,0),(1,1),(2,3),(2,2),(3,3),(4,7),(4,5),(4,4),(5,5),(6,7),(6,6),(7,7)の15個ありますが、
(0,0) = (0,0)
(0,1) = (0,1)
(0,2) = (0,1)+(2,2)
(0,3) = (0,3)
(0,4) = (0,3)+(4,4)
(0,5) = (0,3)+(4,5)
(0,6) = (0,3)+(4,5)+(6,6)
(0,7) = (0,7)
となっており、8種類しか使っていません。
https://algo-logic.info/binary-indexed-tree/
こちらのページにある図を見ると分かりやすいのですが、セグ木で左右に枝分かれするときの右側のノードは、実は0から区間を計算するときには使われないのです。

BITと呼ばれるデータ構造はこのことに注目し、0から区間でしか計算できない代わりに、使われない個所を削ったものになります。

・BITの実装

http://hos.ac/slides/20140319_bit.pdf
これが分かりやすいです。

各ノードにへんてこな順序を付けると、
下位から見て初めて1があるbitが何番目かで、区間の長さが分かり
区間の長さから、次に更新/探索する位置が分かります。

下位から見て初めて1があるbitが何番目かは、

x&-x

とすると分かります。x=10の場合、
x= 10=1010
x=-10=0110
   &を取ると、0010となります。
絵を書けばわかりますが、10の区間の長さは2です。マイナスの補数表現によって、上手いこと炙り出せています。

上記のことを踏まえて、実装は以下になります。

void bit_init(int N,int a){
   seqv.clear();
   int n=N+1;
   seqv_n=n;
   for(int i=0;i<n;i++){
       seqv.push_back(a);
   }
}
void bit_update(int n,int a){
   seqv[n]+=a;
   while(n<=seqv_n){
       n+=(n&-n);
       seqv[n]+=a;
   }
}
int bit_find(int y){
   int ret=0;
   while(y>0){
       ret+=seqv[y];
       y-=(y&-y);
   }
   return ret;
}

上記BITを用いて

signed main(){
   int Q;
   cin>>Q;
   bit_init(200000,0);
   for(int i=0;i<Q;i++){
       int T,X;
       cin>>T>>X;
       if(T==1){
           bit_update(X,1);
       }
       else{
           int l=0;
           int r=200000;
           while(1){
               int mid=(l+r)/2;
               int n=bit_find(mid);
               if(n>=X){
                   if(r==mid) break;
                   r=mid;
               }
               else{
                   if(l==mid) break;
                   l=mid;
               }
           }
           cout<<r<<endl;
           bit_update(r,-1);
       }
   }
}

とすることでACが取れました。
セグ木ではメモリ7036 KB、速度634 msに対し、
BITではメモリ4876 KB、速度366 msでした。
時間的にもメモリ的にもセグ木より優れているといえます。

なお、値の更新の際に、セグ木は左右のノードを見て再計算するのに対し、BITは上に値を伝播させていきます。そのため、削除時にノードに設定する値が少し異なります。

・BITのついで

https://note.com/nullkara/n/n35a61d04c3a8
前に記載したABC174のF問題がそうなのですが、累積和の性質を使えば(0,N)区間しか求められませんが、好きな区間の和を求めることができます。
例えば、区間(4,8)を知りたい場合は、区間(0,8)-区間(0,3)とすれば良いです。

そのため、BITは競プロでは任意区間の累積和を高速に簡単に求めるデータ構造として使われています。(多分)

・さいごに

ABC174のFのnoteを書いていたときはBITの動きが理解できませんでしたが、今なら何となくわかります。