题目链接https://www.luogu.com.cn/problem/P3372

线段树模板

已知一个数列，你需要进行下面两种操作：

1. 将某区间每一个数加上 k。
2. 求出某区间每一个数的和。

输入格式

第一行包含两个整数n,m,分别表示该数列数字的个数和操作的总个数。

第二行包含n个用空格分隔的整数，其中第i个数字表示数列第i项的初始值。

接下来m行每行包含3或4个整数，表示一个操作，具体如下：

1. 1 x y k：将区间 [x, y][x,y] 内每个数加上k。
2. 2 x y：输出区间 [x, y][x,y] 内每个数的和。

输出格式

输出包含若干行整数，即为所有操作 2 的结果。

输入样例

5 5
1 5 4 2 3
2 2 4
1 2 3 2
2 3 4
1 1 5 1
2 1 4

输出样例

11 8 20

0<=n,m<=10⁵

下面是完整代码

 

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN=1e6+3;
struct Node{
	int sum,addv;
}v[MAXN<<2];
int a[MAXN];
void add(int l,int r,int k,int rt){
	v[rt].sum+=(r-l+1)*k;
	v[rt].addv+=k;
}
void push_up(int rt){
	v[rt].sum=v[rt<<1].sum+v[(rt<<1)+1].sum;
}
void push_down(int l,int r,int rt){
	int mid=(l+r)>>1;
	if(v[rt].addv){
		add(l,mid,v[rt].addv,rt<<1);
		add(mid+1,r,v[rt].addv,(rt<<1)+1);
		v[rt].addv=0;
	}
}
void build_tree(int l,int r,int rt){
	if(l==r){
		v[rt].sum=a[l];
		return;
	}
	int mid=(l+r)>>1;
	build_tree(l,mid,rt<<1);
	build_tree(mid+1,r,(rt<<1)+1);
	push_up(rt);
}
void update(int L,int R,int k,int l,int r,int rt){
	if(l>=L&&r<=R){
		add(l,r,k,rt);
		return;
	}
	int mid=(l+r)>>1;
	push_down(l,r,rt);
	if(L<=mid) update(L,R,k,l,mid,rt<<1);
	if(R>=mid+1) update(L,R,k,mid+1,r,(rt<<1)+1);
	push_up(rt);
}
int query(int L,int R,int l,int r,int rt){
	if(l>=L&&r<=R){
		push_down(l,r,rt);
		return v[rt].sum;
	}
	int ans=0,mid=(l+r)>>1;
	push_down(l,r,rt);
	if(L<=mid) ans+=query(L,R,l,mid,rt<<1);
	if(R>=mid+1) ans+=query(L,R,mid+1,r,(rt<<1)+1);
	return ans;
}
int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	build_tree(1,n,1);
	for(int i=1;i<=m;i++){
		int opt;
		scanf("%d",&opt);
		int l,r,k;
		if(opt==1){
			scanf("%d%d%d",&l,&r,&k);
			update(l,r,k,1,n,1);
		}
		if(opt==2){
			scanf("%d%d",&l,&r);
			printf("%d\n",query(l,r,1,n,1));
		}
	}
	return 0;
}

依次来说一下这个结构体和若干个函数的作用

struct node，sum为此节点所覆盖的区间总和，addv一般被称为lazy标记，用于区间加时暂时存储需要加的数字

pushup函数的内容就是把线段树这个二叉树的左子节点和右子节点加和

add函数就是给当前节点加和加上lazy标记

pushdown函数作用在于将父节点的lazy标记传递给两个子节点

update和Query更新查询一套