前往：我自己搭建的博客
题目
洛谷P3372线段树1
题解
线段树的区间修改操作：需要用到延迟标记（先标记修改的位置，不做完整的修改，等待时机顺便操作）。在区间修改时，如果当前节点代表的区间包含于被修改的区间，则修改此区间的值，但不继续递归修改其子节点的信息，而是在当前节点上打个标记。在查询或新增修改时，如果递归到一个节点有标记，则顺便修改其子节点的信息并标记子节点。这样可以减少递归修改子节点信息的时间。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
int n,m;
ll a[maxn];
struct Segment_tree{int l,r; ll sum,add;}t[maxn<<2];
void build(int p,int l,int r)
{
t[p].l=l; t[p].r=r;
if(l==r) {t[p].sum=a[l]; return;}
int mid=(l+r)>>1;
build(p<<1,l,mid); build(p<<1|1,mid+1,r);
t[p].sum=t[p<<1].sum+t[p<<1|1].sum;
}
inline void spread(int p) //从节点p下传延迟标记
{
if(!t[p].add) return;
t[p<<1].add+=t[p].add,t[p<<1|1].add+=t[p].add;
t[p<<1].sum+=t[p].add*(t[p<<1].r-t[p<<1].l+1);
t[p<<1|1].sum+=t[p].add*(t[p<<1|1].r-t[p<<1|1].l+1);
t[p].add=0;
}
void change(int p,int l,int r,ll k)
{
if(l<=t[p].l&&r>=t[p].r) {t[p].sum+=k*(t[p].r-t[p].l+1); t[p].add+=k; return;}
spread(p); int mid=(t[p].l+t[p].r)>>1;
if(l<=mid) change(p<<1,l,r,k);
if(r>mid) change(p<<1|1,l,r,k);
t[p].sum=t[p<<1].sum+t[p<<1|1].sum;
}
ll ask(int p,int l,int r)
{
if(l<=t[p].l&&r>=t[p].r) return t[p].sum;
spread(p); ll ans=0,mid=(t[p].l+t[p].r)>>1;
if(l<=mid) ans+=ask(p<<1,l,r);
if(r>mid) ans+=ask(p<<1|1,l,r);
return ans;
}
int main()
{
scanf("%d%d",&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 t,x,y; ll k; scanf("%d",&t);
if(t==1) {scanf("%d%d%lld",&x,&y,&k); change(1,x,y,k);}
else {scanf("%d%d",&x,&y); printf("%lld\n",ask(1,x,y));}
}
return 0;
}
