セグメント木を育てる 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の動きが理解できませんでしたが、今なら何となくわかります。