线段树及其应用

\#include<bits/stdc++.h>

\#define int long long

\#define md tr\[u].l+((tr\[u].r-tr\[u].l)>>1)//注意是当前节点的中点作为当前区间的分割线

using namespace std;

const int N=1e5+10;

struct node//节点

{

 	int l,r,data,lazy;

}tr\[N<<2];//一定要开四倍空间!!!

int a\[N];

void pushup(int u)//由子节点更新父节点的数据

{

 	tr\[u].data=tr\[u<<1].data+tr\[u<<1|1].data;

}

void pushdown(int u)//下放懒标记

{

 	tr\[u<<1].lazy+=tr\[u].lazy;

 	tr\[u<<1|1].lazy+=tr\[u].lazy;//懒标记直接传给下一代

 	tr\[u<<1].data+=tr\[u].lazy\*(tr\[u<<1].r-tr\[u<<1].l+1);

 	tr\[u<<1|1].data+=tr\[u].lazy\*(tr\[u<<1|1].r-tr\[u<<1|1].l+1);//孩子数据更新

 	tr\[u].lazy=0;//清空下放过的懒标记

}

void build(int u,int l,int r)//建树

{

 	if(l==r)//不能再分割了

 	{

 		tr\[u]={l,r,a\[l],0};//直接赋值

 		return;

 	}

 	tr\[u]={l,r,0,0};

 	int mid=md;

 	build(u<<1,l,mid);//递归左右孩子

 	build(u<<1|1,mid+1,r);

 	pushup(u);//一定不要忘了用子节点更新父节点(u)

}

void modify(int u,int l,int r,int x)//区间修改(单点修改可以看做l=r时的特殊情况)

{

 	if(r<tr\[u].l||l>tr\[u].r)//修改的区间不在当前节点范围内

 	{

 		return;

 	}

 	if(l<=tr\[u].l\&\&r>=tr\[u].r)//当前节点被完全包含于查询区间

 	{

 		tr\[u].lazy+=x;//打懒标记, 避免时间浪费

 		tr\[u].data+=x\*(tr\[u].r-tr\[u].l+1);//更新区间的汇总数据

 		return;

 	}

 	pushdown(u);//修改的时候一定要先下放懒标记qaq(有事有可能对修改有影响)!

 	modify(u<<1,l,r,x);//修改范围不用折半, 因为上面用if特判过了

 	modify(u<<1|1,l,r,x);

 	pushup(u);//修改完了一定要更新一下父节点

}

int query(int u,int l,int r)

{

 	if(r<tr\[u].l||l>tr\[u].r)//同理, 没被包含舍弃

 	{

 		return 0;

 	}

 	if(l<=tr\[u].l\&\&r>=tr\[u].r)//同理, 完全包含直接返回节点汇总值

 	{

 		return tr\[u].data;

 	}

 	pushdown(u);//查询时一定要下方懒标记才能查到真实值

 	return query(u<<1,l,r)+query(u<<1|1,l,r);//合并左右子树的数据, 注意查询区间不折半(同修改, 上面特判过了)

}

signed main()

{

 	int n,m;

 	scanf("%lld %lld",\&n,\&m);

 	for(int i=1;i<=n;i++)

 	{

 		scanf("%lld",\&a\[i]);

 	}

 	build(1,1,n);

 	for(int i=1;i<=m;i++)

 	{

 		int op,x,y;

 		scanf("%lld %lld %lld",\&op,\&x,\&y);

 		if(op==1)

 		{

 			int k;

 			scanf("%lld",\&k);

 			modify(1,x,y,k);//第一个参数是当前节点编号

 		}

 		else

 		{

 			printf("%lld\\n",query(1,x,y));

 		}

 	}

 	return 0;

}