数列求和【線分樹基礎】

//      ：     
#include
#define maxn 10007//     
#define ls l,m,rt<<1
#define rs m+1,r,rt<<1|1
int sum[maxn<<2],add[maxn<<2];//sum  ，add     
int a[maxn],n;//       1  

//PushUp       ，      。             
void PushUp(int rt)
{ 
	sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}

//Build    
void Build(int l,int r,int rt)
{
	if(l==r){
		sum[rt]=a[l];
		return;
	}
	int m=(l+r)>>1;
	//    
	Build(ls);
	Build(rs);
	//     
	PushUp(rt); 
}

//   ， A[L]+=c
void Update1(int L,int c,int l,int r,int rt)
{
	if(l==r){//     ，   
		sum[rt]+=c;
		return;
	}
	int m=(l+r)>>1;
	//                    
	if(L<=m) 
	  Update1(L,c,ls);
	else
	  Update1(L,c,rs);
	PushUp(rt);//      ，               
}
//      
void PushDown(int rt,int ln,int rn)
{
	//ln,rn        
	if(add[rt]){
		//    
		add[rt<<1]+=add[rt];
		add[rt<<1|1]+=add[rt];
		//      sum      add   
		sum[rt<<1]+=add[rt]*ln;
		sum[rt<<1|1]+=add[rt]*rn;
		//       
		add[rt]=0; 
	} 
 } 

//    
void Update2(int L,int R,int C,int l,int r,int rt)
{
	if(L<=l&&r<=R){//            [L,R]  
		sum[rt]+=C*(r-l+1);//     ，       
		add[rt]+=C;//  add  ，      sum   
		return; 
	}
	int m=(l+r)>>1;
	PushDown(rt,m-l+1,r-m);//    
	//       [L,R]    ，      
	if(L<=m) 
	  Update2(L,R,C,ls);
	if(R>m) 
	  Update2(L,R,C,rs);
	PushUp(rt);//        
}

//      
int Query(int L,int R,int l,int r,int rt)
{
	if(L<=l&&r<=R)//    ，    
	  return sum[rt];
	int m=(l+r)>>1;
	//    ，  sum     
	PushDown(rt,m-l+1,r-m);
	//    
	int ans=0;
	if(L<=m)
	  ans+=Query(L,R,ls);
	if(R>m)
	  ans+=Query(L,R,rs);
	return ans; 
}

int main()
{
	n=100;
	for(int i=1;i<=n;i++)
	  a[i]=i;
	//  
	Build(1,n,1);
	int ans=Query(1,100,1,n,1);
	printf("%d
",ans);
	return 0;
	 
}