可持久化线段树

在这里，所谓“可持久化”的数据结构并非指将数据存在非易失的存储器上，而是指保存了数据修改的历史信息。比如说对可持久化线段树进行修改操作，操作完成后我们可以在线段树原有的时间复杂度内查询到希望查询的版本的信息，比如“第二次修改后区间L和R之间的和”。

通常遇到的线段树都是构建之后结构不变化的，所以在修改关键值时，只有节点内的值受到影响，而树本身的结构不发生变化（比如左右子节点所表示的区间）。这为线段树进行可持久化提供了便利。我们每次修改的时候不直接改动原来节点的值，而是创建一系列新的节点。如果整棵树复制的话不仅非常耗费时间，而且占用空间太大。在线段树的单次修改中，实际上受到影响的节点是有限的，原来的节点可以得到重复利用。

修改的过程

可持久化线段树每次修改都会自上而下地新建一些节点。每次修改后的版本都有一个根节点与之对应。

只考虑单点修改，我们将递归过程中所有的节点创建一个“影子节点”，所谓“影子节点”保存的是当前修改结束后的受到更改的值。当u是v的影子节点时，我们称v时u的原节点。

对一棵线段树进行的两次可能发生的修改操作，注意到每个根节点都对应了一次修改，不同的修改操作用了不同的颜色进行区分

在线段树的修改操作中，子节点修改完成后只影响到父节点（pushup操作），而不会影响到兄弟节点。所以我们发现，当修改影响到非叶子结点u时，（在单点修改中）他一定只有一个子节点会受到修改的影响，比如右子节点受到影响，此时u的影子节点v的左子节点指向u的左子节点，而v的右子节点对应的是受到影响的新右子节点w，w是u的右子节点的影子节点，以此类推。

Lazy标签

对于区间修改，需要维护一个lazy标签来推迟更新操作，在pushdown操作时，创建了u的原节点的子节点的影子节点，在实际实现中，通过维护一个节点的origin节点指针就可以做到这一点。

红色是一个标记了lazy的操作，操作结束后并没有立刻生成子节点的影子节点。而在pushdown操作时（紫色），新的影子节点的值从原节点修改而来

实现

由于可持久化线段树在修改过程中需要不断新建影子节点，所以通常的下标标记子节点的方法不再有效。节点需要维护的不仅仅是线段树的关键值x，还有左右子节点指针lch、rch，lazy标记和原节点指针origin。

在修改线段树时，沿着最新版本的线段树自上而下地遍历、创建影子节点并修改即可。

下面的程序实现了一个维护区间和的可持久化线段树，支持区间修改。而且这个程序包含了一个demo。首先输入一个n，随后输入n个整数，表示a[1]~a[n]的初始值。随后开始查询和修改操作，输入q查询，m修改。查询接受一个版本号（从0开始），输出序列所有的值。修改接受u、v和w，表示将区间[u,v]每个元素加上w。

#include <bits/stdc++.h>
using namespace std;
// 可持久化线段树
const int N = 100010;
struct Node {
    int sum, lch, rch, lazy, origin;
    Node():sum(0),lch(-1),rch(-1),lazy(0),origin(-1) {}
}tree[(N<<2)*4];
int tot, a[N], rt[N], curver;

void init() { tot=0; curver=0; }
int createIndentity(int p) {    // 创建影子节点
    int cp=tot++;
    tree[cp]=Node();
    tree[cp].origin=p;tree[cp].sum=tree[p].sum;tree[cp].lazy=tree[p].lazy;
    return cp;
}
void pushup(int p) { tree[p].sum=tree[tree[p].lch].sum+tree[tree[p].rch].sum; }
void pushdown(int p,int l,int r,int m) {
    int lch=tree[p].lch, rch=tree[p].rch;
    if (lch==-1||rch==-1) {
        int o=tree[p].origin;
        lch=tree[p].lch=createIndentity(tree[o].lch);
        rch=tree[p].rch=createIndentity(tree[o].rch);
    }
    tree[lch].lazy+=tree[p].lazy; tree[rch].lazy+=tree[p].lazy;
    tree[lch].sum+=tree[p].lazy*(m-l+1); tree[rch].sum+=tree[p].lazy*(r-m);
    tree[p].lazy=0;
}
int build(int l, int r) {
    int p=tot++;
    tree[p]=Node();
    tree[p].sum=a[l];
    if (l==r) return p;
    int mid=l+r>>1;
    tree[p].lch=build(l,mid);
    tree[p].rch=build(mid+1,r);
    pushup(p);
    return p;
}
int add(int p, int l, int r, int x, int y, int z) {
    int cp=tot++;       // create shadow node
    tree[cp]=Node();
    tree[cp].origin=p;  // origin node number, prepared for pushdown operation
    if (x<=l&&r<=y){
        tree[cp].lazy=tree[p].lazy+z;
        tree[cp].sum=tree[p].sum+z*(r-l+1);
        return cp;
    }
    int mid=l+r>>1;
    if (tree[p].lazy) pushdown(p,l,r,mid);
    if (x<=mid)
        tree[cp].lch=add(tree[p].lch,l,mid,x,y,z);
    else tree[cp].lch=tree[p].lch;
    if (mid<y)
        tree[cp].rch=add(tree[p].rch,mid+1,r,x,y,z);
    else tree[cp].rch=tree[p].rch;
    pushup(cp);
    return cp;
}
int query(int p, int l, int r, int x, int y) {
    if (x<=l&&r<=y) return tree[p].sum;
    int mid=l+r>>1, ret=0;
    if (tree[p].lazy) pushdown(p,l,r,mid);
    if (x<=mid) ret+=query(tree[p].lch,l,mid,x,y);
    if (mid<y) ret+=query(tree[p].rch,mid+1,r,x,y);
    return ret;
}

int main() {
    int n;
    scanf("%d", &n);
    for (int i=1;i<=n;++i) scanf("%d", a+i);
    // 
    init();
    rt[curver]=build(1,n);
    for (;;){
        int u,v,w;
        char q[3];
        printf("q/m:");
        scanf("%s", q);
        if (q[0]=='m') {
            printf("Please input u, v, w and we will add w to [u,v]: ");
            scanf("%d%d%d", &u, &v, &w);
            rt[curver+1]=add(rt[curver],1,n,u,v,w);
            ++curver;
            for (int i=1;i<=n;++i) {
                printf("%d ", query(rt[curver],1,n,i,i));
            }
            puts("");
        }else {
            printf("Please input ver: ");
            scanf("%d", &w);
            for (int i=1;i<=n;++i) {`
                printf("%d ", query(rt[w],1,n,i,i));
            }
            puts("");
        }
    }
    return 0;
}

Have fun！