僕のセグメントツリーの使い方

14:49追加:

ちなみに未だに閉区間使ってるので、閉区間で損したくない人はこの記事の閉区間で書かれたソースは参考にしないほうがいいです！！

（座標圧縮とかの時に、区間が少し被ったりしてバグって損します。春合宿の僕みたいに。）

セグメントツリーは、"できるだけ大きい区間で取って誤魔化す"のも大切ですが、それに加えて"遅延評価"をかなり意識すればいろんな木が簡単に特に思考なしでかけるイメージがあります。

ちなみにここから説明するセグメントツリーは少し弄るだけで色んな変形が出来るのですきですが、冗長なので定数倍遅いです。ごめんなさい。

#include <iostream>
using namespace std;

#define N (1<<17) 
// update(l,r,v) := [l,r]の区間に対してvを一様に足す. k,a,bは飾り

struct NODE{
	int sum;//更新された値. この値を参照する時は評価が完全に完了しているようにする.
	int lazy;	//遅延されている値を保存している
	NODE(){
		sum = lazy = 0;
	}
};

NODE seg[2*N];

// inlineつけないと大変なことになるよ!(遅い)
inline void lazy_evaluate_node(int k,int a,int b){
	seg[k].sum += seg[k].lazy * (b-a+1);
	if( k < N ){ // 2*k(左の子番号) < 2*N (節点の数) のイメージで. 末端ノードじゃなきゃ伝搬するのと等価.
		seg[2*k].lazy += seg[k].lazy;	//次は君が伝搬してね☆って感じ.
		seg[2*k+1].lazy += seg[k].lazy;
	}
	seg[k].lazy = 0;
}

inline void update_node(int k){ // kの子が既に評価されていることが前提. 末端以外のときしか呼び出さないような位置に書くのでif文要らない.
	seg[k].sum = seg[2*k].sum + seg[2*k+1].sum;
}

// update(l,r,v) := [l,r]を更新する. 区間は1-indexed.
void update(int l,int r,int v,int k=1,int a=1,int b=N){ 
	lazy_evaluate_node(k,a,b); 	// とりあえず辿ったノードは都合がいいので伝搬しとけ精神.
	
	if( b < l || r < a ) //[a,b]と[l,r]が交差している場合
		return; 
	if( l <= a && b <= r ){ // [l,r]が[a,b]を完全に含んでいる場合
		seg[k].lazy  += v;
		lazy_evaluate_node(k,a,b); //一回遅延評価しとかないと都合悪いので.
		return;
	}
	
	int m = (a+b)/2;
	update(l,r,v,2*k,a,m);
	update(l,r,v,2*k+1,m+1,b);
	update_node(k);
}

// get(l,r) := [l,r]に対するクエリの答えを得る. 区間は1-indexed.
int get(int l,int r,int k=1,int a=1,int b=N){
	lazy_evaluate_node(k,a,b); // とりあえず辿ったノードは都合がいいので伝搬しとけ精神.
	
	if( b < l || r < a ) //[a,b]と[l,r]が交差している場合
		return 0; 
	
	if( l <= a && b <= r ){ // [l,r]が[a,b]を完全に含んでいる場合
		return seg[k].sum;
	}
	
	int m = (a+b)/2;
	int vl = get(l,r,2*k,a,m);
	int vr = get(l,r,2*k+1,m+1,b);
	update_node(k);
	return vl+vr;
}


int main(){
	update(1,100,1);
	
	int a,b;
	while(cin >> a >> b){
		cout << get(a,b) << endl;
	}
}

これただある区間に一様にxを足して、ある区間の総和取るだけのセグメントツリーです。

アイデアとしては,

各節点のsumは、"その区間での"現在の正しい値を持つ←この値ならサボれるというところが重要
lazyは、その区間に評価を遅延している(=加えていない)ものを持つ。
再帰で根から辿りながら、遅延評価を辿った頂点の子に振りまいていきながら、こまめに節点の本当の値を再計算。必要になったときだけ細かく計算すればよいという感じ。
それをupdateとgetの中でする。

みたいな。

動くイメージはこのスライドを見てくれるとうれしいです(紙芝居にした)→セグツリーイメージ

節点通るときに、とりあえずそいつの子までは、交差してなかろうとしてようと、遅延評価とりあえずしまくる感じですね。

　この形を数行書き換えて、スターリースカイ木と同等の木が書けます。もちろん遅いです。注目するべきは大体lazy_evaluate_node関数とupdate_node関数です。利便性のために関数の引数が変わってますが本質は全く変わっていません。

#include <iostream>
using namespace std;

#define INF (1<<30)
#define N (1<<17) 

struct NODE{
	int maximum;//更新された値. この値を参照する時は評価が完全に完了しているようにする.
	int lazy;	//遅延されている値を保存している
	NODE(){
		maximum = lazy = 0;
	}
};

NODE seg[2*N];

void lazy_evaluate_node(int k){
	seg[k].maximum += seg[k].lazy;
	if( k < N ){ // 2*k(左の子番号) < 2*N (節点の数) のイメージで. 末端ノードじゃなきゃ伝搬するのと等価.
		seg[2*k].lazy += seg[k].lazy;	//次は君が伝搬してね☆って感じ.
		seg[2*k+1].lazy += seg[k].lazy;
	}
	seg[k].lazy = 0;
}

inline void update_node(int k){ // kの子が既に評価されていることが前提. 末端以外のときしか呼び出さないような位置に書くのでif文要らない.
	seg[k].maximum = max(seg[2*k].maximum,seg[2*k+1].maximum);
}

// update(l,r,v) := [l,r]を更新する. 区間は1-indexed.
inline void update(int l,int r,int v,int k=1,int a=1,int b=N){ 
	lazy_evaluate_node(k); 	// とりあえず辿ったノードは都合がいいので伝搬しとけ精神.
	
	if( b < l || r < a ) //[a,b]と[l,r]が交差している場合
		return; 
	if( l <= a && b <= r ){ // [l,r]が[a,b]を完全に含んでいる場合
		seg[k].lazy  += v;
		lazy_evaluate_node(k); //一回遅延評価しとかないと都合悪いので.
		return;
	}
	
	int m = (a+b)/2;
	update(l,r,v,2*k,a,m);
	update(l,r,v,2*k+1,m+1,b);
	update_node(k);
}

// get(l,r) := [l,r]に対するクエリの答えを得る. 区間は1-indexed.
int get(int l,int r,int k=1,int a=1,int b=N){
	lazy_evaluate_node(k); // とりあえず辿ったノードは都合がいいので伝搬しとけ精神.
	
	if( b < l || r < a ) //[a,b]と[l,r]が交差している場合
		return -INF; 
	
	if( l <= a && b <= r ){ // [l,r]が[a,b]を完全に含んでいる場合
		return seg[k].maximum;
	}
	
	int m = (a+b)/2;
	int vl = get(l,r,2*k,a,m);
	int vr = get(l,r,2*k+1,m+1,b);
	update_node(k);
	return max(vl,vr);
}


int main(){
	int N;
	for(int i = 1 ; i <= 100 ; i++)
		update(i,i+1,i);
	
	int a,b;
	while(cin >> a >> b){
		cout << get(a,b) << endl;
	}
}

他にも、前回のCFのような木・もしくはsp12のFortune Tellingの木も少しの変形で解けて、注目するべきは大体lazy_evaluate_node関数とupdate_node関数です。

#include <iostream>
#include <cstdio>
using namespace std;

#define N (1<<17) 
struct NODE{
	int bitsum;//更新された値. この値を参照する時は評価が完全に完了しているようにする.
	int lazy;	//遅延されている値を保存している
	NODE(){
		bitsum = lazy = 0;
	}
};

NODE seg[21][2*N];

//速度的にinline重要. Codeforcesで3000ms -> 2000msになった.
inline void lazy_evaluate_node(NODE *seg,int k,int a,int b){ // ←ちょっとaとbの値が欲しいので追加.
	if( seg[k].lazy ) seg[k].bitsum = (b-a+1) - seg[k].bitsum;
	if( k < N ){ // 2*k(左の子番号) < 2*N (節点の数) のイメージで. 末端ノードじゃなきゃ伝搬するのと等価.
		seg[2*k].lazy ^= seg[k].lazy;	//次は君が伝搬してね☆って感じ.
		seg[2*k+1].lazy ^= seg[k].lazy;
	}
	seg[k].lazy = 0;
}

inline void update_node(NODE *seg,int k){ // kの子が既に評価されていることが前提. 末端以外のときしか呼び出さないような位置に書くのでif文要らない.
	seg[k].bitsum = seg[2*k].bitsum + seg[2*k+1].bitsum;
}

// update(l,r) := [l,r]を更新する. 区間は1-indexed.
void update(NODE *seg,int l,int r,int k=1,int a=1,int b=N){ 
	lazy_evaluate_node(seg,k,a,b); 	// とりあえず辿ったノードは都合がいいので伝搬しとけ精神.
	
	if( b < l || r < a ) //[a,b]と[l,r]が交差している場合
		return; 
	if( l <= a && b <= r ){ // [l,r]が[a,b]を完全に含んでいる場合
		seg[k].lazy  ^= 1;
		lazy_evaluate_node(seg,k,a,b); //一回遅延評価しとかないと都合悪いので.
		return;
	}
	
	int m = (a+b)/2;
	update(seg,l,r,2*k,a,m);
	update(seg,l,r,2*k+1,m+1,b);
	update_node(seg,k);
}

// get(l,r) := [l,r]に対するクエリの答えを得る. 区間は1-indexed.
int get(NODE *seg,int l,int r,int k=1,int a=1,int b=N){
	lazy_evaluate_node(seg,k,a,b); // とりあえず辿ったノードは都合がいいので伝搬しとけ精神.
	
	if( b < l || r < a ) //[a,b]と[l,r]が交差している場合
		return 0; 
	
	if( l <= a && b <= r ){ // [l,r]が[a,b]を完全に含んでいる場合
		return seg[k].bitsum;
	}
	
	int m = (a+b)/2;
	int vl = get(seg,l,r,2*k,a,m);
	int vr = get(seg,l,r,2*k+1,m+1,b);
	update_node(seg,k);
	return vl+vr;
}

てきとうでごめんなさい