同步：https://buringstraw.win/archives/78/
写了棵可持久化线段树，因为模拟赛里用到了主席树，而我却从来没写过。。。
凭借自己对当年上过的课的印象写的，因为翻了很多博客没看懂

概述

每当有修改操作时，把需要修改的节点复制一份，在新复制的节点上完成修改操作。这里的修改也包括对点与点连接结构的修改。然后将每个版本的根节点存入root数组。

结构

这棵线段树需要动态开点，所以要有struct

struct node {
    int l, r;//对应的区间
    int ch[2];//0:左儿子,1:右儿子
    int v;//值
} c[MAXN];

然后要有装初始元素的数组和root数组

int a[MAXN], root[MAXN];

还要记录最新的节点和最新的版本

int newp, newv

操作

所有操作中都要注意：递归操作之后newp会改变

建树

跟普通线段树差不多
要先将根节点的l,r初始化好

root[++newv] = ++newp;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) {
    scanf("%d", a + i);
}
c[newp].l = 1;
c[newp].r = n;

void build (int p) {
    if (c[p].l == c[p].r) {
        c[p].v = a[c[p].l];
    }
    else {
        ++newp;
        int son = newp;//保存当前节点。newp变化之后就不能用了
        c[son].l = c[p].l;
        c[son].r = (c[p].l + c[p].r) >> 1;
        c[p].ch[0] = son;
        build(son);
        c[p].v += c[son].v;
        ++newp;
        son = newp;
        c[son].l = ((c[p].l + c[p].r) >> 1) + 1;
        c[son].r = c[p].r;
        c[p].ch[1] = son;
        build(son);
        c[p].v += c[son].v;
    }
}

查询

跟普通线段树差不多
非常优雅地分成两个函数

int rq(int p, int l, int r) {
    if (c[p].l >= l && c[p].r <= r) {//完全在范围内
        return c[p].v;
    }
    else if (c[p].r < l || c[p].l > r)  {//完全在范围外
        return 0;
    }
    else {
        int s = 0;
        s += rq(c[p].ch[0], l, r);
        s += rq(c[p].ch[1], l, r);
        return s;
    }
}

int query (int v, int l, int r) {
    return rq(root[v], l, r);
}

修改

跟普通线段树唯一不一样的地方

int ra (int p, int x, int k) {//返回值：在当前版本中，修改了之后新建的节点
    if (c[p].l == c[p].r && c[p].l == x) {
        c[++newp] = c[p];
        c[newp].v += k;
        return newp;
    }
    else {
        if (c[p].r < x || c[p].l > x) return p;//没有修改当然继续用原节点啦
        else {
            int son = ++newp;
            c[son] = c[p];
            c[son].ch[0] = ra(c[p].ch[0], x, k);//更新自己的儿子
            c[son].ch[1] = ra(c[p].ch[1], x, k);
            c[son].v = c[c[son].ch[0]].v + c[c[son].ch[1]].v;
            return son;
        }
    }
}

void add (int v, int x, int k) {
    int p = root[v];
    root[++newv] = ra(p, x, k);//新版本的根节点
}

其他

但这样并不能做到区间修改。
但那道模板题不需要
要区间修改的话，照常打lazytag，查询的时候也不用新建版本。很简单。。
另外，每次写这种长数据结构，都会觉得写成指针会更好看

双倍经验

P3834 【模板】可持久化线段树 1（主席树）
P3919 【模板】可持久化数组（可持久化线段树/平衡树）
由于我用整体二分A过主席树那道了所以就没有双倍经验了嘤嘤嘤