首页 > 其他分享 >关于pushdown函数

关于pushdown函数

时间:2023-02-12 22:45:10浏览次数:47  
标签:函数 int tree dat add 关于 pushdown mul

pushdown 函数在在线段树平衡树等数据结构中极为常见,由于本蒟蒻在刚开始学的时候没有理解其的奥妙,于是准备将曾经的疑惑讲出来,也算是弥补了。

首先,pushdown 通常用于修改,最常见的就是加减,他们的优势在于我们需要它的时候,才提前修改它的值,否则不鸟他。
这是一份常见的区间加减代码:

void change(int p,int l,int r,int k){
	if(tree[p].l>=l&&tree[p].r<=r){
		tree[p].dat+=k*(tree[p].r-tree[p].l+1),tree[p].add+=k;
		return;
	}
	pushdown(p);
	int mid=tree[p].l+tree[p].r>>1;
	if(l<=mid)change(p*2,l,r,k);
	if(r>mid)change(p*2+1,l,r,k);
	pushup(p);
} 

其中 \(tree[p].l,tree[p].r\) 意思是本区间的左右端点,\(tree[p].dat,tree[p].add\) 分别是当前区间总和和要传给儿子的值,\(p\times2,p\times2+1\) 是左孩子和右孩子,\(k\) 是要加的值。我们找到在范围内的区间直接下传值和给区间总和加好,然后直接退出,为什么可以这样?看区间查询代码便知。

int query(int p,int l,int r){
	if(tree[p].l>=l&&tree[p].r<=r)return tree[p].dat;
	int res=0,mid=tree[p].l+tree[p].r>>1;
	pushdown(p);
	int mid=tree[p].l+tree[p].r>>1;
	if(l<=mid)res+=query(p*2,l,r);
	if(r>mid)res+=query(p*2+1,l,r);
	return res;
}

可以发现,我们在查询前提前将搜到的地方 pushdown,这样我们查到的答案就是修改完的。

这样我们就不需要 \(\mathcal{O}(n)\) 去修改区间值了。

这时又会心生疑惑,如果在修改时不进行 pushdown 操作会怎么样呢,按道理来讲它好像也可以做对啊?
但是有一个严重的问题,如图:

我们先给区间 \([5,8]\) 加上 \(1\),再给区间 \([8,8]\) 加上 \(1\),此时我们给区间五和八加上 \((8-5+1)\times1\),在下一次 change,我们从顶到 \([8,8]\) 并没有进行 pushdown,所以此时我们的 \([8,8]\) 的值是 \(1\),在进行 pushup 的时候,容易发现我们的区间 \([5,8]\) 的值又被修改成 \(1\) 了,所以我们在加之前必须 pushdown。

区间加减乘的 pushdown

void pushdown(int p){
	if(tree[p].add!=0||tree[p].mul!=1){	
		tree[p*2].dat=(tree[p*2].dat*tree[p].mul)%h;
		tree[p*2+1].dat= (tree[p*2+1].dat*tree[p].mul)%h;
		tree[p*2].dat=(tree[p*2].dat+tree[p].add*(tree[p*2].r-tree[p*2].l+1))%h;
		tree[p*2+1].dat=(tree[p*2+1].dat+tree[p].add*(tree[p*2+1].r-tree[p*2+1].l+1))%h;
		tree[p*2].mul=(tree[p*2].mul*tree[p].mul)%h;
		tree[p*2+1].mul=(tree[p*2+1].mul*tree[p].mul)%h;
		tree[p*2].add=(tree[p*2].add*tree[p].mul)%h;
		tree[p*2+1].add=(tree[p*2+1].add*tree[p].mul)%h;
		tree[p*2].add=(tree[p*2].add+tree[p].add)%h;
		tree[p*2+1].add=(tree[p*2+1].add+tree[p].add)%h;
		tree[p].add=0;
		tree[p].mul=1;
	}
}

它的原则是现乘再加 \(or\) 减,为何要这样?现在就来说说其正确性,看起来就很正确,我们发现在乘的时候或 pushdown 的时候我们给 \(add\) 也乘了要乘的数,所以这么操作是正确的。

pushdown 函数不仅应用于线段树,还可以应用于平衡树等,原理都是一样的,重在理解。

标签:函数,int,tree,dat,add,关于,pushdown,mul
From: https://www.cnblogs.com/lalaouyehome/p/17114898.html

相关文章