Segment Tree(未完)

目次

• 説明

• 注意点

• コード

説明

注意点

• 要素数は2のべき乗ごとになっている。

入力の最大が50だとする。MAX_Nを50とすると定義域外を参照してしまう。入力の大きさが50の時のnは64となる。この状態でupdate(50,0)を呼び出すと、kの値は113となってしまう。なので、MAX_Nは入力の最大値を考慮してしっかりと設計しなければならない。

コード

#include <algorithm>
 
using namespace std;
 
#define INF (1<<20)
#define MAX_N 500000
 
int n,dat[2*MAX_N];
 
void
init(int _n)
{
  n = 1;
	while (n < _n)
		n *= 2;
	for (int i=0; i<2*n-1; ++i) {
		dat[i] = INF;
	}
}
 
void
update(int k,int a)
{
	k += n - 1;
	dat[k] = a;
	while (k > 0) {
		k = (k-1)/2;
		dat[k] = min(dat[k*2+1],dat[k*2+2]);
	}
}
 
int
query(int a,int b,int k,int l,int r)
{
	if (r <= a || b <= l) {
		return INF;
	}
	if (a <= l && r <= b) {
		return dat[k];
	}
	else {
		int vl = query(a, b, k*2+1, l, (l+r)/2 );
		int vr = query(a, b, k*2+2, (l+r)/2, r );
		return min(vl,vr);
	}
}