第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次元平面に対してある区域内の点の個数を求める、とか)

遅延seg木

ある区間内の総和、ある区間への加算、みたいなクエリに対して答えろ、という問題とかがこれで解けます。
(seg木を二つ持てば解けるとかそういう無粋なことは言わない)

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);
}