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