【数据结构】线段树

线段树是算法竞赛中常用的用来维护 区间信息 的数据结构．

线段树可以在$O(\log n)$ 的时间复杂度内实现单点修改、区间修改、区间查询（区间求和，求区间最大值，求区间最小值）等操作．

区间修改 区间求和

P3372 【模板】线段树 1

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

• 将某区间每一个数加上 𝑘．
• 求出某区间每一个数的和．

// Problem:P3372 【模板】线段树 1
// Contest:Luogu
// URL:https://www.luogu.com.cn/problem/P3372
// Memory Limit:512 MB
// Time Limit:1000 ms

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN=1e5+10;
int n,m,a[MAXN+10],val[(MAXN<<2)+10],tag[(MAXN<<2)+10],len[(MAXN<<2)+10];
int ls(int i){return i<<1;}
int rs(int i){return i<<1|1;}
int read()
{
	int x=0,f=1;
	char c=getchar();
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c)){x=x*10+c-'0',c=getchar();}
	return x*f;
}
void add_tag(int pos,int num)//增加懒标记
{
	tag[pos]+=num;
	val[pos]+=len[pos]*num;
}
void pushup(int pos)
{
	val[pos]=val[ls(pos)]+val[rs(pos)];
}
void pushdown(int pos)//下传懒标记
{
	if(!tag[pos])return ;
	add_tag(ls(pos),tag[pos]);
	add_tag(rs(pos),tag[pos]);
	tag[pos]=0;
}
void build(int pos,int l,int r)
{
	len[pos]=r-l+1;
	if(l==r){val[pos]=a[l];return ;}
	int mid=l+((r-l)>>1);
	build(ls(pos),l,mid);
	build(rs(pos),mid+1,r);
	pushup(pos);
}
void modify(int pos,int ql,int qr,int l,int r,int num)
{
	if(qr<l||r<ql)return ;
	if(ql<=l&&qr>=r){add_tag(pos,num);return ;}//[ql,qr]包含当前区间
	int mid=l+((r-l)>>1);
	pushdown(pos);
	modify(ls(pos),ql,qr,l,mid,num);
	modify(rs(pos),ql,qr,mid+1,r,num);
	pushup(pos);
}
int query(int pos,int ql,int qr,int l,int r)
{
	if(qr<l||r<ql)return 0;
	if(ql<=l&&qr>=r)return val[pos];
	int mid=l+((r-l)>>1);
	pushdown(pos);
	return query(ls(pos),ql,qr,l,mid)+query(rs(pos),ql,qr,mid+1,r);
}
signed main()
{
	n=read(),m=read();
	for(int i=1;i<=n;i++)a[i]=read();
	build(1,1,n);
	while(m--)
	{
		int opt=read();
		if(opt==1)
		{
			int l=read(),r=read(),num=read();
			modify(1,l,r,1,n,num);
		}
		else
		{
			int l=read(),r=read();
			cout<<query(1,l,r,1,n)<<'\n';
		}
	}
	return 0;
}