主题

主题

 
   

标记永久化的线段树

  • 扯淡

无意中看到了CJ大佬的一篇文章,《标记永久化的线段树》。然后自己感兴趣写了一下。


  • 原理

在写Seg的时候一般都有一个标记下传的操作——pushdown。

不过事实上我们发现,如果只是计算对结果的影响的话,如果当前穿过了一个标记,就把这个标记加上影响就可以了。


  • 实现

首先是unite函数。此时每一个节点的sum等于子节点的sum加上自己的tag*区间长度len。

即:

void unite(int p) {

    Seg[p].sum=Seg[Seg[p].s[0]].sum+Seg[Seg[p].s[1]].sum+Seg[p].tag*(Seg[p].r-Seg[p].l+1);

}

这样就可以不下传标记同样使得当前这个标记上方的节点都是正确的。

接下来是Getsum函数。把穿过这个区间时要做的pushdown函数变为一个+的操作。

即:

long long Getsum(int p,int l,int r) {

    if(Seg[p].l==l&&Seg[p].r==r)return Seg[p].sum;

    long long sum=Seg[p].tag*(r-l+1);//在这里先把tag加上

    if(r<=Seg[p].m)sum+=Getsum(Seg[p].s[0],l,r);

    else if(Seg[p].m+1<=l)sum+=Getsum(Seg[p].s[1],l,r);

    else {

        sum+=Getsum(Seg[p].s[0],l,Seg[p].m);

        sum+=Getsum(Seg[p].s[1],Seg[p].m+1,r);

    }

    return sum;

}

大体就是这样的变化。

然后又A了一遍codevs_1082……

代码如下:

https://code.csdn.net/snippets/2222185

 
 
评论
 
 
热度(1)