非再帰版セグメントツリーテンプレート

ここから
(0)定義:

#define maxn 100007
int A[maxn],n,N;//   ,n         ,N        
int Sum[maxn<<2];//    
int Add[maxn<<2];//    

(1)ツリーの作成:

void Build(int n){
	//  N   
	N=1;while(N < n+2) N <<= 1;
	//      
	for(int i=1;i<=n;++i) Sum[N+i]=A[i];//     +N=    
	//       
	for(int i=N-1;i>0;--i){
		//              
		Sum[i]=Sum[i<<1]+Sum[i<<1|1];
		//         Add   
		Add[i]=0;
	}
} 

(2)点修正:

A[L]+=C
void Update(int L,int C)
{
	for(int s=N+L;s;s>>=1)
		Sum[s]+=C;
} 

(3)点修正下の区間照会:
A[L…R]の和を求めます(点の修正はAddを使っていないので考慮する必要はありません)
コードは非常に簡潔で、理解しにくいわけではありません.
sとtはそれぞれ前の論述の左右の青色ノードを表し,残りのコードは前の論述に基づいて容易に理解できるはずである.
st 1はsとtの父親が同じ時間に0となり,ループを終了する.
2つのifは,sとtがそれぞれ左サブノードであるか右サブノードであるかを判断し,必要に応じてSumを計算する.

int Query(int L,int R){
	int ANS=0;
	for(int s=N+L-1,t=N+R+1;s^t^1;s>>=1,t>>=1){
		if(~s&1) ANS+=Sum[s^1];
		if( t&1) ANS+=Sum[t^1];
	}
	return ANS;
} 

(4)区間修正:

A[L..R]+=C
void Update(int L,int R,int C){
	int s,t,Ln=0,Rn=0,x=1;
	//Ln:  s            
	//Rn:  t            
	//x:              
	for(s=N+L-1,t=N+R+1;s^t^1;s>>=1,t>>=1,x<<=1){
		//  Sum
		Sum[s]+=C*Ln;
		Sum[t]+=C*Rn;
		//  Add
		if(~s&1) Add[s^1]+=C,Sum[s^1]+=C*x,Ln+=x;
		if( t&1) Add[t^1]+=C,Sum[t^1]+=C*x,Rn+=x;
	}
	//    Sum
	for(;s;s>>=1,t>>=1){
		Sum[s]+=C*Ln;
		Sum[t]+=C*Rn;
	} 
}

(5)区間修正下の区間照会:
A[L…R]の和を求めます

int Query(int L,int R){
	int s,t,Ln=0,Rn=0,x=1;
	int ANS=0;
	for(s=N+L-1,t=N+R+1;s^t^1;s>>=1,t>>=1,x<<=1){
		//       
		if(Add[s]) ANS+=Add[s]*Ln;
		if(Add[t]) ANS+=Add[t]*Rn;
		//     
		if(~s&1) ANS+=Sum[s^1],Ln+=x;
		if( t&1) ANS+=Sum[t^1],Rn+=x; 
	}
	//      
	for(;s;s>>=1,t>>=1){
		ANS+=Add[s]*Ln;
		ANS+=Add[t]*Rn;
	}
	return ANS;
}