线段树模板

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1e5;
struct Tree
{
	int l,r;
	long long add,sum;
	#define l(x) (tree[x].l)
	#define r(x) (tree[x].r)
	#define add(x) (tree[x].add)
	#define sum(x) (tree[x].sum)
}tree[N*4+10];
int a[N+10],n,m;
void build(int p,int l,int r)
{
	l(p)=l; r(p)=r;
	if(l==r) 
	{
		sum(p)=a[l];
		return;
	}
	int mid=(l+r)/2;
	build(p*2,l,mid);
	build(p*2+1,mid+1,r);
	sum(p)=sum(p*2)+sum(p*2+1);
}
void spread(int p)
{
	if(add(p))
	{
		sum(p*2)+=add(p)*(r(p*2)-l(p*2)+1);
		sum(p*2+1)+=add(p)*(r(p*2+1)-l(p*2+1)+1);
		add(p*2)+=add(p);
		add(p*2+1)+=add(p);
		add(p)=0; 
	}
}
long long ask(int p,int l,int r)
{
	if(l<=l(p) && r>=r(p)) return sum(p);
	spread(p);
	int mid=(l(p)+r(p))/2;
	long long ans=0;
	if(l<=mid) ans+=ask(p*2,l,r);
	if(r>mid) ans+=ask(p*2+1,l,r);
	return ans;
}
void change(int p,int l,int r,int d)
{
	if(l<=l(p) && r>=r(p))
	{
		sum(p)+=(long long)d*(r(p)-l(p)+1);
		add(p)+=d;
		return;
	}
	spread(p);
	int mid=(l(p)+r(p))/2;
	if(l<=mid) change(p*2,l,r,d);
	if(r>mid) change(p*2+1,l,r,d);
	sum(p)=sum(p*2)+sum(p*2+1);
}
int main()
{
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	build(1,1,n);
	for(int i=1;i<=m;i++)
	{
		int p;
		scanf("%d",&p);
		if(p==1)
		{
			int x,y,k;
			scanf("%d %d %d",&x,&y,&k);
			change(1,x,y,k);
		}
		else
		{
			int x,y;
			scanf("%d %d",&x,&y);
			printf("%lld\n",ask(1,x,y));
		}
	}
	return 0;
}

线段树模板

原文：https://www.cnblogs.com/juruo-zzt/p/12936460.html