可持久化线段树

定义

可以回到某个历史版本的线段树，可以知道前几次修改的情况。
这将使线段树有更灵活的应用。

做法

不难发现，其实，每次修改，我们更改的点，就是从叶子到根的一条路径，只有logn的点改变了，其他还是原样。
做法就出来了，把修改变为插入logn个改变的点，并连接到上次修改的，旧的树上，这样就相当于多了一颗新树。
图的话可以看此文背景。
有几个版本，我们就有了几棵线段树

每一次修改，都多了个根结点，每个根结点对应一个历史版本。
查询就直接在该版本的树根上查找就好了。

复杂度？（n是大小，m是询问）
空间(n+mlogn)——1棵大小为n线段树+m个大小为logn的历史版本的线段树。对于100000的规模可以简单的写成20n
时间(mlogn)——跟线段树一样。

实现

对于原始版本，需要一次Build，建立一颗完整的树。

会与线段树有不同，也就是把Updata变为Ins，以单点修改为x例。
void Ins(int last_node,int &new_node,int x)
插入新点，需要知道与它在同一位置的旧点，就可以得知原树的信息了。

int Ins(int op,int p) //更改位置p的数 
{
    int np=tptr++; //新建结点 

    tr[np]=tr[op]; //保留旧的信息 

    Tnode &old=tr[op];

    if (old.l<old.r)
    {
        int mid=(old.l+old.r)>>1;

        if (mid<p) tr[np].rc=Ins(old.rc,p); //指向新的点 
              else tr[np].lc=Ins(old.lc,p);
    }

    Updata(np); //整理信息 

    return np; //个人喜好写返回
}
rt[i]=Ins(rt[j],p)； //用法

运用

区间的区间

在序列里求一段数L~R里数字x出现的个数？大于x（且小于y）的数有几个？

想象一个以数值为下标的数组z，问x有几个，就是z[x]。
根据前缀和的思想，a[i]是记录1~i的数的z数组，用a[R]-a[L-1]，就可以获得这一段的z数组。

所以，每一个a[i]就相当于历史版本，装进可持久化线段树里，就可以了。

二元组问题

即矩形数点问题，在平面直角坐标系里，给定一些点的坐标，问一个矩形里有多少个点。 con(p) (x[L1]<=px<=x[R1] && y[L2]<=py<=y[R2])

用扫描线可以离线解决，用可持久化线段树，树套树在线解决。

其实，就是上面说的区间的区间问题，以x做历史版本答案就是Sum(rt[R1],L2,R2)-Sum(rt[L1-1],L2,R2)

区间第k大

可持久化线段树的版子题，根据区间的区间的启发，我们可以知道这个区间每个数出现的次数，然后二分即可。需要先离散化。
这里二分可以用树划分（利用线段树二分，就省去求和的时间！！！）
所以总的时间mlogn就可以了。

灵活脑洞

国家集训队：middle
欠。可自行研究。

总结

暴力插入即可。

CC 原创文章采用CC BY-NC-SA 4.0协议进行许可，转载请注明：“转载自：可持久化线段树”

• ← Previous Post
• Next Post →