首页 算法

朴素版的线段树只能实现单点修改区间查询，修改和查询的时间复杂度都是 O (logn)

# 懒标记问题

加上懒标记后的线段树就可以实现区间修改了，比如我要把 [a,b] 的值加上 k，肯定不会傻到 n 次单点修改，是个人都会想到假如递归到一个包含在 [a,b] 的区间时就不用继续往下递归了，直接告诉这个区间的管理员，把这个区间的和直接给修改了，但是假如你上面第一次增加时增加区间为 [c,d]，并且区间 [c,d] 是包含在 [a,b] 中间的，现在又要在 [e,d] 增加 k，e>c 的，这个时候你就会发现 [e,d] 这个区间增加了两次，因为第一次增加时你根本没有递归到 [e,d]，而是递归到这个区间的上一层就直接返回了，现在你再在 [e,d] 区间增加值就会出错，因为少加了第一次的增值，所以应该找一个东西记录下来第一次增值，并且把他带到下面去，这时懒标记就出来了，新开一个数组 lazy [i]，表示编号为 i 的区间的累计增值，那么第一次修改 [c,d] 时，lazy [u](u 表示区间 [c,d] 的编号) 就会记录下来增值，lazy [u]+=c，第二次修改经过这个已经修改过的区间时，就要顺带着把这个区间的修改值一起带过去，正所谓父亲欠下的债儿子去偿还，当修改 [e,d] 时，经过 [c,d] 区间时，就会把 lazy 值给带到下面的儿子区间里面

void pushdown(u){
	tr[u<<1].val+=lazy[u];  // 儿子区间加上父亲区间的增值
	tr[u<<1|1].val+=lazy[u];
	lazy[u<<1]=lazy[u];  // 儿子区间也要加上标记，当以后再经过儿子区间时也要顺带增值去修改
	lazy[u<<1|1].val+=lazy[u];
    lazy[u]=0;  // 既然父亲的债给儿子了，父亲也就没有债了
}

这就是区间查询的灵魂了，朴素版和 plus 只差了几行代码而已，首先修改时判断区间条件变了，只要当前区间处于修改区间内就可以直接修改，修改时把区间值增加区间长度 * 增值，并把加法标记 lazy 累加即可

# 线段树 1

一道模板题线段树 1

#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
using namespace std;
typedef long long ll;
const ll SUP=0x800000;
const ll MAXN=1e5+10;
const ll INF=0x3f3f3f3f;
const double eps=1e-4;
struct node{
	ll l,r,val;
}tr[MAXN<<2];
ll lazy[MAXN<<2],arr[MAXN];
void pushup(ll u){
	tr[u].val=tr[u<<1].val+tr[u<<1|1].val;
}
void pushdown(ll u){  // 区间修改灵魂代码
	if(lazy[u]){
		tr[u<<1].val+=(tr[u<<1].r-tr[u<<1].l+1)*lazy[u];
		lazy[u<<1]+=lazy[u];
		tr[u<<1|1].val+=(tr[u<<1|1].r-tr[u<<1|1].l+1)*lazy[u];
		lazy[u<<1|1]+=lazy[u];
		lazy[u]=0;
	}
}
void build(ll u,ll l,ll r){
	if(l==r) tr[u]={l,r,arr[l]};
	else{
		tr[u]={l,r};
		ll mid=(l+r)>>1;
		build(u<<1,l,mid);
		build(u<<1|1,mid+1,r);
		pushup(u); 
	}
}
void add(ll u,ll l,ll r,ll c){
	if(tr[u].l>=l && tr[u].r<=r){
		tr[u].val+=(tr[u].r-tr[u].l+1)*c;  // 值加上区间长度 * 增值
		lazy[u]+=c; // 标记累加
	}
	else{
		pushdown(u);  // 往下传时要顺带着把增值带过去
		ll mid=(tr[u].l+tr[u].r)>>1;
		if(r<=mid) add(u<<1,l,r,c);
		else if(l>mid) add(u<<1|1,l,r,c);
		else{
			add(u<<1,l,r,c);
			add(u<<1|1,l,r,c);
		}
		pushup(u);
	}
}
ll query(ll u,ll l,ll r){
	if(tr[u].l>=l && tr[u].r<=r) return tr[u].val;
	else{
		pushdown(u);  // 记得查询函数也要往下传，只要往区间下面递归的都要 pushdown!
		ll mid=(tr[u].r+tr[u].l)>>1;
		if(r<=mid) return query(u<<1,l,r);
		else if(l>mid) return query(u<<1|1,l,r);
		else{
			ll ret1=query(u<<1,l,r);
			ll ret2=query(u<<1|1,l,r);
			return ret1+ret2;
		}
	}
}
int main()
{
	ios;
	ll n,m;
	cin>>n>>m;
	for(ll i=1;i<=n;i++) cin>>arr[i];
	build(1,1,n); 
	while(m--){
		ll op;
		cin>>op;
		if(op==1){
			ll x,y,k;
			cin>>x>>y>>k;
			add(1,x,y,k);
		}
		else{
			ll x,y;
			cin>>x>>y;
			cout<<query(1,x,y)<<'\n';
		}
	}
	return 0;
 }

# 线段树 2

接下来看一道比较难的升级版本线段树 2

image-20210119174455193

这道题只是增加了一个操作，不只可以给一段区间增加值，也可以乘上一个值，假如两种运算分开考的话那么这道题就是一道模板题，但难就难在他一起考了，你一定会想到这就会涉及到优先级问题，因为假如给一段区间增加了一个值，又给这段区间乘上一个值，之后递归时经过这个区间时，你就弄不清楚应该先加还是先乘，而这两种结果显然是不同的，假设儿子区间的值为 a，父亲区间已经有了加法标记 b 和乘法标记 c，那么两种不同的运算顺序会得到不同结果

(a+b)∗c!=a∗c+b(a+b)*c!=a*c+b

那么有没有办法规定一种固定的运算顺序，使得无论是先给父亲区间加上加法标记还是乘法标记最终得到相同的结果呢？

答案是有的，观察上面不等式两边的式子发现只要在右面的 b 后面乘上一个 c 两个式子就相等了，因此我们就可以规定一种运算，永远先乘再加，当添加标记的顺序就是先乘再加时肯定没问题，但是若先添加的加法标记然后添加的乘法标记时怎么办？这时候计算儿子的值时就是 儿子的值*乘值+儿子区间长度*增值 ，假如先加后乘那么儿子的值应该是 (儿子的值+儿子区间长度*增值)*乘值 ，发现了吗？实际和理想只差了一个乘法标记，所以当先添加加法标记再添加乘法标记时，把已经添加的加法标记乘上乘值即可使得两种不同的顺序得到相同的结果，儿子的加法标记更新时就要先乘以父亲乘法标记再加上父亲加法标记，你可能会问为什么有这种情况，向下传递时父亲标记不是被传递给儿子了吗？但传递后还可以再给啊！传递后我再让父亲区间加上或者乘上一个值，这也是合法的，所以当再次经过父亲区间时儿子区间的加法标记还没有乘上父亲的增值，就需要补充上去，而乘法标记只需要乘以父亲乘法标记即可

# 核心代码

void pushdown(ll u){
	ll l=u<<1,r=u<<1|1;
	// 儿子的值=儿子的值*父亲的乘法标记+儿子区间*父亲加法标记 
	tr[l].val=(tr[l].val*lazy2[u]%p+(tr[l].r-tr[l].l+1)*lazy1[u]%p)%p;
	tr[r].val=(tr[r].val*lazy2[u]%p+(tr[r].r-tr[r].l+1)*lazy1[u]%p)%p;
	// 儿子加法标记更新，儿子加法标记=儿子加法标记*父亲乘法标记+父亲加法标记 
	lazy1[l]=(lazy1[l]*lazy2[u]%p+lazy1[u])%p;
	lazy1[r]=(lazy1[r]*lazy2[u]%p+lazy1[u])%p;
	//  儿子乘法标记=儿子乘法标记*父亲乘法标记
	lazy2[l]=lazy2[l]*lazy2[u]%p;
	lazy2[r]=lazy2[r]*lazy2[u]%p;
	
	lazy1[u]=0;
	lazy2[u]=1;
}

为什么不先加后乘呢？因为这样就涉及到了除法运算，就出现了精度问题，会出错。

# ACCODE

#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
using namespace std;
typedef long long ll;
const ll MOD=1e9+7;
const ll SUP=0x800000;
const ll MAXN=1e5+10;
const ll INF=0x3f3f3f3f;
const double eps=1e-4;
struct node{
	ll l,r,val;
}tr[MAXN<<2];
//lazy1 加法标记 lazy2 乘法标记 
ll lazy1[MAXN<<2],lazy2[MAXN<<2],arr[MAXN];
ll n,m,p;
void pushup(ll u){
	tr[u].val=(tr[u<<1].val+tr[u<<1|1].val)%p;
}
void pushdown(ll u){
	ll l=u<<1,r=u<<1|1;
	// 儿子的值 = 儿子的值 * 父亲的乘法标记 + 儿子区间 * 父亲加法标记 
	tr[l].val=(tr[l].val*lazy2[u]%p+(tr[l].r-tr[l].l+1)*lazy1[u]%p)%p;
	tr[r].val=(tr[r].val*lazy2[u]%p+(tr[r].r-tr[r].l+1)*lazy1[u]%p)%p;
	// 儿子加法标记更新，儿子加法标记 = 儿子加法标记 * 父亲乘法标记 + 父亲加法标记 
	lazy1[l]=(lazy1[l]*lazy2[u]%p+lazy1[u])%p;
	lazy1[r]=(lazy1[r]*lazy2[u]%p+lazy1[u])%p;
	//  儿子乘法标记 = 儿子乘法标记 * 父亲乘法标记
	lazy2[l]=lazy2[l]*lazy2[u]%p;
	lazy2[r]=lazy2[r]*lazy2[u]%p;
	
	lazy1[u]=0;
	lazy2[u]=1;
}
void build(ll u,ll l,ll r){
	lazy1[u]=0;  // 初始化标记 
	lazy2[u]=1;
	if(l==r) tr[u]={l,r,arr[l]};
	else{
		tr[u]={l,r};
		ll mid=(l+r)>>1;
		build(u<<1,l,mid);
		build(u<<1|1,mid+1,r);
		pushup(u); 
	}
}
void add(ll u,ll l,ll r,ll c){
	if(tr[u].l>=l && tr[u].r<=r){
		tr[u].val=(tr[u].val+(tr[u].r-tr[u].l+1)*c%p)%p;  // 区间值加上 c 
		lazy1[u]=(c+lazy1[u])%p;  // 更新加法标记 
	}
	else{
		pushdown(u);
		ll mid=(tr[u].l+tr[u].r)>>1;
		if(l<=mid) add(u<<1,l,r,c);
		if(r>mid) add(u<<1|1,l,r,c);
		pushup(u);
	}
}
void mul(ll u,ll l,ll r,ll c){
	if(tr[u].l>=l && tr[u].r<=r){
		tr[u].val=tr[u].val*c%p;  // 区间的值乘上 c 
		lazy1[u]=(lazy1[u]*c)%p;  // 每次更新乘法标记时要顺带着把加法标记也更新了，目的是确定优先级 
		lazy2[u]=(lazy2[u]*c)%p;  // 更新乘法标记 
	}
	else{
		pushdown(u);
		ll mid=(tr[u].l+tr[u].r)>>1;
		if(l<=mid) mul(u<<1,l,r,c);
		if(r>mid) mul(u<<1|1,l,r,c);
		pushup(u);
	}
}
ll query(ll u,ll l,ll r){
	if(tr[u].l>=l && tr[u].r<=r) return tr[u].val;
	else{
		pushdown(u);
		ll mid=(tr[u].r+tr[u].l)>>1,ret=0;
		if(l<=mid) ret=(ret+query(u<<1,l,r))%p;
		if(r>mid) ret=(ret+query(u<<1|1,l,r))%p;
		return ret;
	}
}
int main()
{
	ios;
	cin>>n>>m>>p;
	for(ll i=1;i<=n;i++) cin>>arr[i];
	build(1,1,n); 
	while(m--){
		ll op,x,y,k;
		cin>>op;
		if(op==1){
			cin>>x>>y>>k;
			mul(1,x,y,k);
		}
		else if(op==2){
			cin>>x>>y>>k;
			add(1,x,y,k);
		}
		else{
			cin>>x>>y;
			cout<<query(1,x,y)<<'\n';
		}
	}
	return 0;
 }
更新于

请我喝[茶]~(￣▽￣)~*

PocketCat 微信支付

微信支付

PocketCat 支付宝

支付宝