可持久化线段树学习笔记

可持久化数据结构

线段树的可持久化改造版本！

入门：可持久化数组

洛谷模板：【模板】可持久化线段树 1（可持久化数组）。

题意：

长度为 \(n\) 的序列 \(\{a\}\)，\(m\) 次操作，支持：

1. 修改某一版本某一位置的值。
2. 访问某一版本某一位置的值。

也就是可持久化的单点修，单点查。

\(n,m \le 10^6\)。

题解：

这个题就是用来入门可持久化线段树的可持久化相关操作的，主要是复制节点。

可持久化数据结构因为内存消耗大，所以推荐把节点表示的区间 \([l,r]\) 作为线段树相关函数的参数，而不是在建树的时候预处理出来，保存在节点中。亲测确实可以节省接近一倍空间（洛谷的数据，极限情况）。而且虽然理论上是预处理节点对应区间并保存时间更优，但是实测把区间作为参数传递给函数还会快一些。

（虽然我不是很习惯把区间作为参数传递，但是改一下也很简单）

代码很简单。

#include 
#define DEBUG puts("QAQ")
#define openFile(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout)
#define NOSYNC ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define FOR(i,j,k)  for(int (i) = (j); (i) <= (k); ++ (i))
#define RFOR(i,j,k) for(int (i) = (j); (i) >= (k); -- (i))
#define For(i,j,k)  for(int (i) = (j); (i) < (k); ++ (i))
#define RFor(i,j,k) for(int (i) = (j); (i) > (k); -- (i))
#define SC(...) scanf(__VA_ARGS__)
#define PR(...) printf(__VA_ARGS__)
#define N 1000005
using namespace std;

struct node {
    int val;
    int lc, rc;
    #define val(p) t[p].val
    #define lc(p) t[p].lc
    #define rc(p) t[p].rc
}t[N << 5];
int tot; int root[N];
int n, m; int a[N];

int copy(int old);
int build(int p, int l, int r);
int modify(int p, int l, int r, int pos, int k);
int query(int p, int l, int r, int pos);

int main()
{
	SC("%d%d", &n, &m);
	FOR(i,1,n) SC("%d", &a[i]);
	root[0] = build(0, 1, n);
	FOR(i,1,m)
	{
	    int ver, op, pos; SC("%d%d%d", &ver, &op, &pos);
	    if(op == 1)
	    {
	        int val; SC("%d", &val);
	        root[i] = modify(root[ver], 1, n, pos, val);
	    }
	    else if(op == 2)
	    {
	        PR("%d\n", query(root[ver], 1, n, pos));
	        root[i] = root[ver];
	    }
	}
	return 0;
}

int copy(int old)
{
   t[++ tot] = t[old];
   return tot;
}

int build(int p, int l, int r)
{
    p = ++ tot;
    if(l == r) 
    {
        val(p) = a[l];
        return p;
    }
    int mid = (l + r) >> 1;
    lc(p) = build(lc(p), l, mid);
    rc(p) = build(rc(p), mid + 1, r);
    return p;
}

int modify(int p, int l, int r, int pos, int k)
{
    p = copy(p);
    if(l == r) 
    {
        val(p) = k;
        return p;
    }
    int mid = (l + r) >> 1;
    if(pos <= mid) lc(p) = modify(lc(p), l, mid, pos, k);
    else           rc(p) = modify(rc(p), mid + 1, r, pos, k);
    return p;
}

int query(int p, int l, int r, int pos)
{
    if(l == r) return val(p);
    int mid = (l + r) >> 1;
    if(pos <= mid) return query(lc(p), l, mid, pos);
    else           return query(rc(p), mid + 1, r, pos);
}

To Be Continued;