<–我写了这么久，就点个赞吧$QwQ$

$1.$ 可持久化线段树简介

可持久化线段树，就是保留历史的线段树。

$2.$ 可持久化线段树的基本概念

可持久化线段树，就是在线段树的每次操作中保留历史记录，并且从第$i$个线段树的根开始访问第$i$个历史版本的线段树，其中初始版本编号为$0$。

$3.$ 可持久化线段树的存储方法

思路

可持久化线段树无法使用普通线段树的堆式存储法，所以要采用动态开点法。即和$\text{trie}$树一样的方法。为了好写，我们把每一个节点表示的区间放到函数的参数内部，这样可以有效减小空间和代码实现难度。
每次修改会多出$\log_2n$个节点，所以我们一共要开$4\times n + m \times \log_2n$个点。

代码

struct segment_tree_node {
    int l,r,sum,add;    //左子节点，右子节点，要维护的信息和懒标记，这里我采用求和
}tr[4 * N + M * MAX_LOG];   //空间要开足
int root[M],idx;    //每次操作的根，当前分配到哪个点了
void push_up (int u) {
    tr[u].sum = tr[tr[u].l].sum + tr[tr[u].r].sum;
}
void push_down (int u,int l,int r) {
    auto &root = tr[u],&left = tr[tr[u].l],&right = tr[tr[u].r];
    int mid = l + r >> 1;
    if (root.add) {
        left.add += root.add,left.sum += (mid - l + 1) * root.add;
        right.add += root.add,right.sum += (r - (mid + 1) + 1) * root.add;
        root.add = 0;
    }
}

$4.$ 建立可持久化线段树

思路

动态开点的线段树建立和普通线段树建立类似，就是变为动态开点罢了，上代码吧。

代码

int build (int l,int r) {   //返回[l,r]区间所组成线段树的编号。
    int u = ++idx;  //动态开点
    if (l == r) return u;
    int mid = l + r >> 1;
    tr[u] = {build (l,mid),build (mid + 1,r),0};    //存下左儿子和右儿子的编号
    return u;
}

$5.$ 单点操作

思路

我们一开始先从要修改的位置，假设是从第$v$次操作的根（$root_v$）开始修改，每次我们先拷贝下当前节点在$root_v$中的位置的节点（一摸一样拷贝），然后把要修改的位置（左儿子或右儿子）递归的修改即可，可以结合代码理解。

代码

int insert (int v,int l,int r,int x,int d) {    //当前已经复制到v，要把第x个数加上d，当前的区间是[l,r]
    int u = ++idx;  //动态开点
    tr[u] = tr[v];  //拷贝节点
    if (l == r) {
        tr[u].sum += d;
        return u;
    }
    push_down (u,l,r);
    int mid = l + r >> 1;
    if (x <= mid) tr[u].l = insert (tr[v].l,l,mid,x,d); //修改左子树
    else tr[u].r = insert (tr[v].l,mid + 1,r,x,d);  //修改右儿子
    push_up (u);
    return u;
}

$6.$ 区间修改

思路

类似线段树的区间修改，就是在单点修改的基础上加上了懒标记而已。

代码

int insert (int v,int l,int r,int L,int R,int d) {    //当前已经复制到v，要把[L,R]加上d，当前的区间是[l,r]
    int u = ++idx;  //动态开点
    tr[u] = tr[v];  //拷贝节点
    if (L <= l && r <= R) {
        tr[u].sum += (R - L + 1) * d;
        tr[u].add += d;
        return u;
    }
    push_down (u,l,r);
    int mid = l + r >> 1;
    if (L <= mid) tr[u].l = insert (tr[v].l,l,mid,L,R,d);
    if (R >= mid + 1) tr[u].r = insert (tr[v].l,mid + 1,r,L,R,d);
    push_up (u);
    return u;
}

$7.$ 单点查询

思路

类似单点修改，返回时要返回查询的答案

代码

int query (int u,int l,int r,int x) { //从第u个历史版本查询，当前区间是[l,r]，查询x的值
    if (l == r) return tr[u].sum;
    push_down (u);
    int mid = l + r >> 1;
    if (x <= mid) return query (tr[u].l,l,mid,x);
    return query (tr[u].r,mid + 1,r,x);
}

$8.$ 区间查询

思路

类似区间修改，返回时要返回查询答案

代码

int query (int u,int l,int r,int L,int R) { //从第u个历史版本查询，当前区间是[l,r]，查询[L,R]的值
    if (L <= l && r <= r)  return tr[u].sum;
    push_down (u);
    int mid = l + r >> 1;
    int ans = 0;
    if (L <= mid) ans += query (tr[u].l,l,mid,L,R);
    if (R >= mid + 1) ans += query (tr[u].r,mid + 1,r,L,R);
    return ans;
}

这是最基础的操作了，如果有误（肯定有误）请提出，本蒟蒻将万分感谢！！！