线段树

题目1：（带懒标记的线段树）

给定一个长度为 NN 的数列 AA，以及 MM 条指令，每条指令可能是以下两种之一：

1. C l r d，表示把 A[l],A[l+1],…,A[r]A[l],A[l+1],…,A[r] 都加上 dd。
2. Q l r，表示询问数列中第 l∼rl∼r 个数的和。

对于每个询问，输出一个整数表示答案。

题目来源：https://www.acwing.com/problem/content/244/

#include<bits/stdc++.h>
#define LL long long 
using namespace std;

const int N = 1e5+1;
int n,m,w[N];

struct node{
	int l,r;
	LL sum,add;
}tr[4*N];

void pushup(int u){
	tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
}

void build(int u,int l,int r){
	if(l==r)
		tr[u]={l,r,w[l],0};
	else{
		tr[u]={l,r};
		int mid = l + r>>1;
		build(u<<1,l,mid);
		build(u<<1|1,mid+1,r);
		pushup(u);
	}
}

void pushdown(int u){
	if(tr[u].add){
		node &left=tr[u<<1],&right=tr[u<<1|1];
		tr[u<<1].add+=tr[u].add,left.sum+=(LL)(left.r-left.l+1)*tr[u].add;
		tr[u<<1|1].add+=tr[u].add,right.sum+=(LL)(right.r-right.l+1)*tr[u].add;
		tr[u].add=0;
	}
} 

void modify(int u,int l,int r,int d){
	if(tr[u].l>= l and tr[u].r<=r){
		tr[u].sum+=(LL)(tr[u].r-tr[u].l+1)*d;
		tr[u].add+=d;
	}
	else{
		int mid = tr[u].l +tr[u].r>>1;
		pushdown(u);
		if(l<=mid)modify(u<<1,l,r,d);
		if(r>mid)modify(u<<1|1,l,r,d);
		pushup(u);
	}
}

LL query(int u,int l,int r){
	if(tr[u].l>= l and tr[u].r<=r)return tr[u].sum;
	int mid=tr[u].l + tr[u].r >> 1;
	LL sum=0; 
	pushdown(u);
	if(l<=mid)sum=query(u<<1,l,r);
	if(r>mid)sum+=query(u<<1|1,l,r);
	pushup(u);
	
	return sum;
}

int main(){
	char op;
	int l,r,d;
	cin>>n>>m;
	for(int i = 1 ; i <= n ; i ++ )
		cin>>w[i];
	build(1,1,n);
	while(m--){
		cin>>op>>l>>r;
		if(op=='Q'){
			cout<<query(1,l,r)<<endl;
		}
		else{
			cin>>d;
			modify(1,l,r,d);
		}
	}
	return 0;
}

　　注意点：1.modify和query中递归都是从l到r，开头的if中的区间都是区间范围在l到r之间；

　　　　　　2.mid是区间中的mid，tr[u].r+tr[u].r>>1；

　　　　　　3.注意不要忘记在main函数中建树build，建树过程中初始化节点tr【u】={xxx}；