セグメントツリーメモ

更新は再帰的に処理します。各操作O(logN)

///RMQ
#define SIZE (1<<18)
#define ll long long
#define INF (1<<30)///必要に応じて増やす

ll int MSEG[SIZE];

void update(int index){
	if(index==0)return;
	int l = index*2,r = index*2+1,tmp = MSEG[index];
	if(MSEG[l]<MSEG[r]){
		MSEG[index] = MSEG[l];
	}else{
		MSEG[index] = MSEG[r];
	}
	if(tmp==MSEG[index])return;///更新が無ければ終了
	update(index/2);
}

ll getMin(int a,int b,int k,int l,int r){
	if(b<l||a>r)return INF;///含まない
	if(a<=l&&r<=b)return MSEG[k];///[a,b]が[l,r]を完全に含む
	ll ml = getMin(a,b,k*2,l,(r-l)/2+l);///左側
	ll mr = getMin(a,b,k*2+1,(r-l)/2+l+1,r);///右側
	return min(ml,mr);
}