板子：可持久化数据结构

可持久化线段树

基本思想

一种牺牲一点空间来达到更多操作的数据结构，似乎可以部分代替平衡树，并且是个在线的过程。至于更多的细节打算以后去拜读cls的大作吧，先把基本的弄了来。

思想就是单点修改只需要修改一部分的点，共用一部分的点，然后用来作各种各样的操作，区间修改也是可以的，但是要稍作改动。

还有就是那个所谓主席树就是指以下标为时间的权值可持久化线段树。

至于觉得可持久化线段树很鸡肋的话，倒也不至于，因为虽然感觉很多，但是实现起来还是很简单的，应该比平衡树简单不少了。而且有些时候的确只能用可持久化数据结构做嘛。

代码

来两段核心代码吧，其它的基本上和普通线段树是一样的。

int copynode(int x)
{
    ++np;
    lc[np]=lc[x],rc[np]=rc[x],cnt[np]=cnt[x]；
    return np;
}
void Modify(int pre,int &now,int L,int R,int i)
{
    now=copynode(pre);
    if(L==R)
    {
        cnt[now]++;
        return;
    }
    int m=(L+R)>>1;
    if(i<=m) Modify(lc[pre],lc[now],L,m,i);
    else Modify(rc[pre],rc[now],m+1,R,i);
    pushup(now);
}

空间复杂度：2n + mlog2n

时间复杂度：都是log2n

一些延伸操作

一、可以由两个根同时往下访问，得到在两个根下的同一区间。

二、关于带pushdown的区间修改

用down标记，pushdown的时候为了不破坏原来的结构，新建两个子结点再常规pushdown，修改的时候只要不是叶子结点就先pushdown下去

我来解释一下：如果后pushdown的话，那么和新结点就没什么关系了，新结点又不会继承down的这个值，所以看起来就像是继承了前面的前面那种情况，当然查询pushdown是可以放在后面的。

至于空间分析：根据每一层都只会访问两个结点（来自《统计的力量》），那么就是2*log2n, 然后每次都可能因为pushdown多做两个子树，再加上本身结点的赋值，那么就是 6 *log2n *m(修改+查询)这么多咯。

三、树上的路径寻找问题
对于不修改的树，可以在父亲结点的基础上建立可持久化线段树（弄一个DFS序出来（最简单的序即可，你非要搞树剖我也没办法啊）），就可以搞了。

代码

贴一下核心代码

void pushdown(int now,int L,int R)
{
    if(down[now])
    {
        lc[now]=copynode(lc[now]);
        rc[now]=copynode(rc[now]);
        int m=(L+R)>>1;
        down[lc[now]]+=down[now];
        sum[lc[now]]+=1ll*down[now]*(m-L+1);
        down[rc[now]]+=down[now];
        sum[rc[now]]+=1ll*down[now]*(R-m);
        down[now]=0;
    }
}
void modify(int pre,int &now,int L,int R,int i,int j,int t)
{
    if(L!=R)pushdown(pre,L,R);
    now=copynode(pre);
    if(i<=L && R<=j)
    {
        sum[now]+=1ll*(R-L+1)*t;
        down[now]+=t;
        return;
    }
    int m=(L+R)>>1;
    if(i<=m) modify(lc[pre],lc[now],L,m,i,j,t);
    if(j>m) modify(rc[pre],rc[now],m+1,R,i,j,t);
    pushup(now);
}
LL Qsum(int now,int L,int R,int i,int j)
{
    if(i<=L && R<=j)
        return sum[now];
    pushdown(now,L,R);
    LL ret=0;
    int m=(L+R)>>1;
    if(i<=m)ret+=Qsum(lc[now],L,m,i,j);
    if(j>m)ret+=Qsum(rc[now],m+1,R,i,j);
    return ret;
}

可持久化数据结构补充

• 可持久化数组：丫的就是可持久化线段树啊
• 可持久化treap：每次把需要修改的结点Newnode出来