WNJXYK
Thanks to the cruel world.
WNJXYKのBlog
标记永久化线段树
标记永久化线段树

对于主席树等数据结构,区间修改的时候打Tag进行维护标记下推和向上合并是非常困难的。如果使用标记永久化技术,就可以避免下推标记和向上合并这两个操作了。

修改

对于修改操作,对[left, right]区间加v
当当前树上节点区间[l, r] \not\in [left, right]的时候,我们直接把区间加的贡献记录在Sum中。
当当前树上节点区间[l, r] \in [left, right]的时候,我们不仅把贡献记录在Sum中,还将v记录进add Tag。

查询

对于查询操作,在从上往下递归查询的过程中,再不断的累和add Tag对查询区间造成的影响。

代码

namespace FTST{
    const int MAXN=2e5+50;
    struct BTree{ LL sum, add; int lx, rx; } tree[MAXN*64]; int nume, root[MAXN];
    void modify(int &x, int y, int l, int r, int left, int right, LL v){
        x=++nume;
        tree[x].add=tree[y].add;
        tree[x].sum=tree[y].sum;
        tree[x].lx=tree[y].lx; tree[x].rx=tree[y].rx;
        tree[x].sum+=v*(right-left+1);
        if (left<=l && r<=right){
            tree[x].add+=v;
        }else{
            int m=(l+r)/2;
            if (right<=m) modify(tree[x].lx, tree[y].lx, l, m, left, right, v);
            else if (m+1<=left) modify(tree[x].rx, tree[y].rx, m+1, r, left, right, v);
            else{
                modify(tree[x].lx, tree[y].lx, l, m, left, m, v);
                modify(tree[x].rx, tree[y].rx, m+1, r, m+1, right, v);
            }
        }
    }

    LL query(int x, int y, int l, int r, int left, int right){
        if (x==y) return 0;
        if (left<=l && r<=right){
            return tree[y].sum-tree[x].sum;
        }else{
            int m=(l+r)/2;
            LL ret=(tree[y].add-tree[x].add)*(right-left+1);

            if (right<=m) ret+=query(tree[x].lx, tree[y].lx, l, m, left, right);
            else if (m+1<=left) ret+=query(tree[x].rx, tree[y].rx, m+1, r, left, right);
            else{
                ret+=query(tree[x].lx, tree[y].lx, l, m, left, m);
                ret+=query(tree[x].rx, tree[y].rx, m+1, r, m+1, right);
            }
            return ret;
        }
    }
}
赞赏
https://secure.gravatar.com/avatar/f83b57c055136369e9feba5d6671d6b5?s=256&r=g

WNJXYK

文章作者

一个蒟蒻

发表评论

textsms
account_circle
email

WNJXYKのBlog

标记永久化线段树
对于主席树等数据结构,区间修改的时候打Tag进行维护标记下推和向上合并是非常困难的。如果使用标记永久化技术,就可以避免下推标记和向上合并这两个操作了。 修改 对于修改操作,对$[l…
扫描二维码继续阅读
2018-09-24
<--! http2https -->