如果你用可持久化线段树+标记永久化,如果你只在最后区间覆盖的时候再更新和打标记,像写普通线段树一样:
void update(int x,int &y,int l,int r,int L,int R,int k){
y=++tot;
lc[y]=lc[x],rc[y]=rc[x],t[y]=t[x],tag[y]=tag[x];
if(L<=l && r<=R){
t[x]+=(ll)(r-l+1)*k;
tag[y]+=(ll)k;
return ;
}
if(L<=mid) update(lc[x],lc[y],l,mid,L,R,k);
if(R>mid) update(rc[x],rc[y],mid+1,r,L,R,k);
pushup(y);
}
这样做错误的原因是,被打标记的这个节点的所有子孙,因受标记永久化的影响没有被更改。导致在下次修改时,如果访问到这些点,因为这些点没有被及时更新,导致把一个没有及时更新的点上传,就会出错。
比如在更新区间 [1,2] 时:
蓝色的部分就因为标记而没有修改。
如果这时候再更新区间 [2,4]:

就会把没有更新的位置 2 带上去,就会出错。
正确的更新应该是遍历一个点就更新,或者带着标记更新。