刍议线段树 2 （区间修改，区间查询）

线段树 \(2\)

接上一讲

https://www.cnblogs.com/yingxilin/p/18350988
（没看的同学们可以先看这篇）

上一讲里我们已经介绍了单点修改，区间查询的线段树了。
在这一讲里，我们开始学习支持区间修改，区间查询的线段树。
考虑之前的做法，之前的查询区间会被分为 \(O(logn)\),从而求解，但因为所有子树节点要一起更新， 复杂度沦为 \(O(n)\) ,无法接受。

tag-懒惰标记

这时，我们可以给要修改的点加一个懒惰标记 \(tag\) ,标记为“该点已经被修改，其子节点尚未被更新”，再将其下传。之后在递归进入其父节点时再判断其是否带有 \(tag\) 标记，若有，再将其更新。如此一来，就不用修改一个点时更新所有子树节点，只需要把要用到的节点更新，大大减小了算法复杂度。具体操作看代码，有注释。

区间更改，区间查询

例题：
https://www.luogu.com.cn/problem/P3372

大意：区间加，区间求和

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define FOR(i,_l,_r) for(int i=_l;i<=_r;i++)
#define ls (p<<1)
#define rs (p<<1|1)
#define mid ((l+r)>>1)//这里一定要记得打上括号，不然会调得很惨
#define len(x) (t[x].r-t[x].l+1)
const int N=1e5+5;
struct Node{
	int l,r;//左右儿子
	int sum,tag;//区间和，懒惰标记
}t[N<<2];
int a[N];
int n,m;
void up(int p){//向上更新
	t[p].sum=t[ls].sum+t[rs].sum;
}
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;
	}
	build(ls,l,mid);
	build(rs,mid+1,r);
	up(p);
}

void down(int p){//懒惰标记下放
	if(!t[p].tag) return;//无tag,return；
	int k=t[p].tag;
	t[ls].sum+=k*len(ls);//更新左区间
	t[rs].sum+=k*len(rs);//更新右区间
	t[ls].tag+=k;//传给左儿子
	t[rs].tag+=k;//传给右儿子
	t[p].tag=0;//记得把当前标记清零
}

void change(int p,int L,int R,int v){//修改
	int l=t[p].l;
	int r=t[p].r;
	if(L<=l&&r<=R){
		t[p].sum+=v*len(p);//更新当前节点的区间和
		t[p].tag+=v;//更新tag
		return;
	}
	down(p);//下放
	if(L<=mid) change(ls,L,R,v);
	if(R>mid) change(rs,L,R,v);
	up(p);
}

int query(int p,int L,int R){//查询
	int l=t[p].l;
	int r=t[p].r;
	if(L<=l&&r<=R)  return t[p].sum;
	down(p);//下放
	int ans=0;
	if(L<=mid) ans+=query(ls,L,R);
	if(R>mid) ans+=query(rs,L,R);
	return ans;
}

signed main(){
	freopen("test.in","r",stdin);
	freopen("test.out","w",stdout);
	// ios::sync_with_stdio(false);
	// cin.tie(NULL);
	cin>>n>>m;
	FOR(i,1,n)  cin>>a[i];
	build(1,1,n);//建树
	while(m--){
		// cout<<1;
		int opt,x,y,k;
		cin>>opt>>x>>y;
		if(opt==1){
			cin>>k;
			change(1,x,y,k);
		}
		else  cout<<query(1,x,y)<<endl;
	}
	return 0;
}