可持久化学习笔记

· · 个人记录

一、可持久化线段树

给一个数组，支持两种操作，并询问区间最大值：

考虑暴力存下每一个时间的线段树，回退时直接用 t 时间的树替换当前的树，但显然空间开不下。

观察到每次修改操作只有 log 级别的节点会受到影响，绝大部分节点不变，于是考虑只新建有变化的点。

发现根的信息一定会变化，即根一定会新建，所以可以单独将每个时间的根的编号存下来，可以用于访问特定时间。

回到本题，对于操作一，从新根向下遍历，新建有变化的点，无变化则直接连向旧树上的点。

对于操作二，直接将当前根用 t 时刻的根替换掉，之后的操作就可以以 t 版本为基础。

#include <bits/stdc++.h> 
#define int long long
using namespace std;
const int N = 40000010;
int n, m, a[N], tag[N], mx[N], tot, ls[N], rs[N], rot[N], la = 0;
//tag: 懒标记，mx：区间最大值，tot：最新节点编号，ls：左儿子，rot：根编号
int clone(int x) {//新建（复制）节点
    tot++;
    tag[tot] = tag[x];
    ls[tot] = ls[x];
    rs[tot] = rs[x];
    mx[tot] = mx[x];
    return tot;
}
void pushup(int x) {mx[x] = max(mx[ls[x]] + tag[ls[x]], mx[rs[x]] + tag[rs[x]]);}//合并
int build(int l, int r) {//建树
    int x = ++tot;//动态开点
    if(l == r) {
        mx[x] = a[l];
        tag[x] = 0;
        return x;
    }
    int mid = (l + r) >> 1;
    ls[x] = build(l, mid);
    rs[x] = build(mid + 1, r);
    pushup(x);
    return x;
}
int modify(int x, int l, int r, int ql, int qr, int v) {//区间加
    x = clone(x);//x节点被修改，所以新开（复制）一个x节点，不会影响到原树
    if(ql <= l && r <= qr) {
        tag[x] += v;//标记永久化
        return x;
    }
    int mid = (l + r) >> 1;
    if(ql <= mid) ls[x] = modify(ls[x], l, mid, ql, qr, v);
    if(mid < qr) rs[x] = modify(rs[x], mid + 1, r, ql ,qr, v);
    //建出或指向原树的新树的左右儿子
    pushup(x);
    return x;//返回新建的x节点
}
int query(int x, int l, int r, int ql, int qr, int laz) {//查询区间最大值
    if(ql <= l && r <= qr) return mx[x] + laz + tag[x];
    int mid = (l + r) >> 1, tmp = -0x7fffffffffff;
    if(ql <= mid) tmp = max(tmp, query(ls[x], l, mid, ql, qr, laz + tag[x]));
    if(mid < qr) tmp = max(tmp, query(rs[x], mid + 1, r, ql ,qr, laz + tag[x]));
    return tmp;
}
signed main() {
    cin >> n >> m;
    for(int i = 1; i <= n; i++) scanf("%lld", &a[i]);
    rot[0] = build(1, n);//以0号节点为根建初始状态（时刻0）的树
    for(int k = 1; k <= m; k++) {
        int tt, l, r, z;
        scanf("%lld%lld%lld%lld", &tt, &l, &r, &z);
        tt = ((tt ^ la) % k + k) % k;
        rot[k] = modify(rot[tt], 1, n, l, r, z);//k版本在tt版本基础上修改
        la = query(rot[k], 1, n, l, r, 0);
        printf("%lld\n", la);
    }
    return 0;
}

有几个要注意的点：动态开点、标记永久化、空间开够。

二、可持久化权值线段树（主席树）

查询区间 [l,r] 内的第 k 小值，无修改。

如果区间只有固定的一个，可以发现能用权值线段树解决。那么，如果每个区间能对应一个权值线段树，那本题就做完了。

考虑可持久化，在序列中，以第 i-1 个位置的树为基础，插入 a_i 便得到了第 i​ 个位置对应的树。

发现权值线段树是可减的，即可以用位置 r 的树减去位置 l-1 的树得到区间 [l,r] 对应的树。

可以把权值线段树类比为一个桶，截取区间的方法类比为前缀和来方便理解。

#include <bits/stdc++.h> 
#define int long long
using namespace std;
const int N = 6400010;
int n, m, rot[N], ls[N], rs[N], num[N], tot, a[N], b[N];
//num：以当前节点为根的子树内含有的数的个数
int clone(int x) {
    int t = ++tot;
    ls[t] = ls[x], rs[t] = rs[x];
    num[t] = num[x] + 1;
    return t;
}
int build(int l, int r) {
    int x = ++tot;
    if(l == r) return x;
    int mid = (l + r) >> 1;
    ls[x] = build(l, mid);
    rs[x] = build(mid + 1, r);
    return x;
}
int modify(int x, int l, int r, int q) {
    x = clone(x);
    if(l == r) return x;//找到q应该在的位置并返回
    int mid = (l + r) >> 1;
    if(q <= mid) ls[x] = modify(ls[x], l, mid, q);
    else rs[x] = modify(rs[x], mid + 1, r, q);
    return x;
}
int query(int x, int y, int l, int r, int k) {
    int mid = (l + r) >> 1;
    int v = num[ls[y]] - num[ls[x]];//相减得到区间[l,r]所对应的树的信息
    if(l == r) return l;
    if(v >= k) return query(ls[x], ls[y], l, mid, k);//权值线段树的查找
    return query(rs[x], rs[y], mid + 1, r, k - v);
}
signed main() {
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        scanf("%lld", &a[i]), b[i] = a[i];
    sort(a + 1, a + n + 1);
    int nm = unique(a + 1, a + n + 1) - a - 1, la = 0;
    rot[0] = build(1, nm);
    for(int i = 1; i <= n; i++) {
        int tmp = lower_bound(a + 1, a + nm + 1, b[i]) - a;//离散化
        rot[i] = modify(rot[i - 1], 1, nm, tmp);//i在i-1版本上更新
    }
    while(m--) {
        int l, r, k, L, R, K;
        scanf("%lld%lld%lld", &l, &r, &k);
        L = l, R = r, K = k;
        la = a[query(rot[L - 1], rot[R], 1, nm, K)];
        printf("%lld\n", la);
    }
    return 0;
}

注意：和可持久化线段树的区分、离散化、需要满足可减性。

三、可持久化并查集

只需要对每个节点维护 fa,dep 即可，fa 用来查找父亲，dep 用于按秩合并保证复杂度。

四、可持久化Trie树

一般是可持久化0/1Trie，用于维护区间异或相关信息。在写法上和主席树类似，即 i+1 版本在 i 基础上插入了一个数或字符。

询问区间也和主席树一样，因为Trie树显然是可减的。可以看一道经典的例题P4735最大异或和来加深理解。

题目给定一个非负整数序列 \{a\}，初始长度为 N。

有 M 个操作，有以下两种操作类型：

  1. A x：添加操作，表示在序列末尾添加一个数 x，序列的长度 N 加 1。
  2. Q l r x：询问操作，你需要找到一个位置 p，满足 l \le p \le r，使得：a[p] \oplus a[p+1] \oplus ... \oplus a[N] \oplus x 最大，输出最大值。

操作一直接在序列末尾插入即可，对于操作二，预处理一个数组 s 表示前缀异或和，转化为寻找 p 使得 s[N]\oplus s[p-1]\oplus x 最大。

由于 S[N]\oplus x 已知，所以只需要将 [l,r] 区间所对应的01Trie截取出来，用 S[N]\oplus x 在其上查找使得异或最大值即可。

#include <bits/stdc++.h> 
using namespace std;
const int N = 40000010;
int n, m, tot, num[N], ch[N][2], rot[N], a[N], s[N];
//num：子树内原节点数
void insert(int x, int y, int v) {//x在y版本基础上插入v
    for(int i = 28; i >= 0; i--) {
        num[x] = num[y] + 1;//类比之前的clone()
        int tmp = ((v & (1 << i)) ? 1 : 0);
        if(tmp) {
            if(!ch[x][1]) ch[x][1] = ++tot;
            ch[x][0] = ch[y][0];//为变化，所以指向旧树
            x = ch[x][1];
            y = ch[y][1];
        }
        else {
            if(!ch[x][0]) ch[x][0] = ++tot;
            ch[x][1] = ch[y][1];
            x = ch[x][0];
            y = ch[y][0];
        }
    }
    num[x] = num[y] + 1;
}
int query(int x, int y, int v) {//在"y-x"的树内查询与v异或最大的值异或v后的结果
    int res = 0;
    for(int i = 28; i >= 0; i--) {
        int tmp = ((v & (1 << i)) ? 1 : 0);
        if(num[ch[x][!tmp]] - num[ch[y][!tmp]])
            res += (1 << i), x = ch[x][!tmp], y = ch[y][!tmp];
        else x = ch[x][tmp], y = ch[y][tmp];
    }
    return res;
}
signed main() {
    cin >> n >> m;
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for(int i = 1; i <= n; i++) s[i] = s[i - 1] ^ a[i];//前缀异或和
    for(int i = 1; i <= n; i++)
        rot[i] = ++tot, insert(rot[i], rot[i - 1], s[i]);//类比主席树
    while(m--) {
        char opt; cin >> opt;
        if(opt == 'A') {//末尾插入
            int x; scanf("%d", &x);
            a[++n] = x;
            s[n] = s[n - 1] ^ x;
            rot[n] = ++tot;
            insert(rot[n], rot[n - 1], s[n]);
        }
        else {//查询
            int l, r, x, res; 
            scanf("%d%d%d", &l, &r, &x);
            l--, r--;
            if(l == 0) res = max(s[n] ^ x, query(rot[r], rot[0], s[n] ^ x));
            else res = query(rot[r], rot[l - 1], s[n] ^ x);
            printf("%d\n", res);
        }
    }
    return 0;
}

五、可持久化平衡树

由于Splay复杂度是均摊的，可持久化后复杂度会错，而旋式Treap的可持久化不好写，所以一般选择非旋Treap来写可持久化。

直接套可持久化的套路，即复制出要修改的节点，其原本节点的儿子若不被修改，则直接指过去，否则继续递归下去。

int new_node(int x = 0) {
    t[++tot] = (node) {...};
    return tot;
}
int clone(int x) {
    int p = new_node();
    t[p] = t[x]; return p;
}
#define ls t[x].l
#define rs t[x].r
void push_down(int x) {
    if(ls) ls = clone(ls);
    if(rs) rs = clone(rs);
    ...
    t[x].tag = 0;
    if(ls) ...
    if(rs) ...
}
void split(int x, int k, int &p1, int &p2) {
    if(!x) {p1 = p2 = 0; return ;}
    if(t[x].tag) push_down(x);
    if(t[ls].siz < k) {
        p1 = clone(x);
        split(t[p1].r, k - t[ls].siz - 1, t[p1].r, p2);
        push_up(p1);
    }
    else {
        p2 = clone(x);
        split(t[p2].l, k, p1, t[p2].l);
        push_up(p2);
    }
}
int merge(int x, int y) {
    if(!x || !y) return x + y;
    if(rnd() % (t[x].siz + t[y].siz) < t[x].siz) {
        push_down(x);
        int p = clone(x);
        t[p].r = merge(t[x].r, y);
        push_up(p);
        return p;
    } 
    else {
        push_down(y);
        int p = clone(y);
        t[p].l = merge(x, t[y].l);
        push_up(p);
        return p;
    }
}

然后有一些要注意的点：

  1. 要注意因为有复制操作，所以要记得在复制前 pushdown。
  2. 发现 merge 中有一句 rnd() % (t[x].siz + t[y].siz) < t[x].siz，是因为复制节点后会出现大量相同的堆值，从而导致树会不平衡，所以不记录堆值，用这种方法代替。
  3. 如果复制操作太多，空间可能会炸，所以在题目不限制的情况下，可以考虑定期重构。 
    void dfs(int x) {
if(!x) return ;
push_down(x);
dfs(t[x].l), tp[++tcnt] = t[x].val, dfs(t[x].r);
}
void rebuild() {
tcnt = 0, dfs(rt), rt = 0, tot = 0;
for(int i = 1; i <= tcnt; i++)
    rt = merge(rt, new_node(tp[i]));
}

六、常见拓展

例一：字符串树（父子关系建树）

给定一棵树，每条边上有一个字符串。每次给出一组询问 (u,v)，求 u\to v 的路径上有多少条边以 S 为前缀。

树的节点个数 n\le 10^5，询问个数 q\le 10^5，所有字符串长度 |S|\le 10。

首先考虑一个简化的问题：在序列上，每个点对应一个字符串，求区间 [l,r]​ 中有多少个字符串以 S​ 为前缀。

显然可以用可持久化Trie解决，对于每个询问，截取出询问所需要的区间所对应的Trie树，将 S​ 放入Trie中，边遍历边统计答案。

然后发现可以将这个思路转化到树上，即每个节点在其父亲的版本上更新，比父亲版本多了连接父子的边的字符串。

预处理出LCA，就可以通过将 u,v 的树分别与 LCA(u,v) 的树相减截取出 LCA(u,v)-u,LCA(u,v)-v​ 这两条链所对应的Trie树。

分别对两条链统计答案并相加即可。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2000010;
int n, q;
int rot[N], ch[N][27], num[N], tot;
string s;
int id = 0, h[N], logg[N], dep[N], f[N][27];
struct node {
    int v, next;
    string c;
}p[N];
void add(int u, int v) {
    id++;
    p[id].v = v;
    p[id].next = h[u];
    p[id].c = s;
    h[u] = id;
}
void init(int x, int fa) {//LCA预处理
    f[x][0] = fa, dep[x] = dep[fa] + 1;
    for(int i = 1; i <= logg[dep[x]]; i++)
        f[x][i] = f[f[x][i - 1]][i - 1];
    for(int i = h[x]; i; i = p[i].next)
        if(p[i].v != fa) init(p[i].v, x);
}
int lca(int x, int y) {//求LCA
    if(dep[x] < dep[y]) swap(x, y);
    while(dep[x] > dep[y]) x = f[x][logg[dep[x] - dep[y]] - 1];
    if(x == y) return x;
    for(int i = logg[dep[x]] - 1; i >= 0; i--)
        if(f[x][i] != f[y][i])
            x = f[x][i], y = f[y][i];
    return f[x][0];
}
void insert(int x, int y) {//x在y的版本上插入s
    int siz = s.size();
    for(int i = 0; i < siz; i++) {
        num[x] = num[y] + 1;
        int o = s[i] - 'a';
        if(!ch[x][o]) ch[x][o] = ++tot;
        for(int j = 0; j < 26; j++)
            if(o != j) ch[x][j] = ch[y][j];
        x = ch[x][o], y = ch[y][o];
    }
    num[x] = num[y] + 1;
}
int query(int x, int y) {//在"y-x"的树上"插入"s并统计答案
    int siz = s.size();
    for(int i = 0; i < siz; i++) {
        int o = s[i] - 'a';
        x = ch[x][o], y = ch[y][o];
    }
    return num[y] - num[x];
}
void dfs(int x) {
    for(int i = h[x]; i; i = p[i].next) {
        if(p[i].v == f[x][0]) continue;
        rot[p[i].v] = ++tot;
        s = p[i].c; insert(rot[p[i].v], rot[x]);//儿子版本在父亲版本上更新
        dfs(p[i].v);
    }
}
signed main() {
    cin >> n;
    for(int i = 1; i < n; i++) {
        int u, v; scanf("%lld%lld", &u, &v);
        cin >> s;
        add(u, v), add(v, u); 
    }
    for(int i = 1; i <= n; i++)
        logg[i] = logg[i - 1] + (1 << logg[i - 1] == i);
    rot[1] = 0;
    init(1, 0); dfs(1);
    cin >> q;
    while(q--) {
        int u, v; scanf("%lld%lld", &u, &v);
        cin >> s;
        int z = lca(u, v), fz = f[z][0];
        //截取链并查询答案
        int t1 = query(rot[z], rot[u]);
        int t2 = query(rot[z], rot[v]);
        printf("%lld\n", t1 + t2);
    }
    return 0;
}

例二：树上统计（可加性）

给定一棵树，每个点有权值。每次给一组询问 (u,v,k)，求 u\to v 之间节点的第 k 小点权，强制在线。

树的节点个数 n\le 10^5，询问个数 q\le 10^5，点权 w_i\le 10^9。

和上一道题一样，根据树的关系建主席树，问题在于如何求解两条链上所有点的第 k 小点权。

显然直接合并两条链对应的权值线段树是不行的，但是思考我们建主席树后为什么可以截取区间，即截取区间为什么有正确性。

原因是主席树的信息是可减的，那么反之主席树的信息也是可加的。那就可以将两棵树相加来达到合并的目的。

体现在代码中即两棵树一起跑，左右儿子的大小都分别是两棵树左右儿子大小的和。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 4000010;
int n, m, tot, ls[N], rs[N], a[N], la = 0, b[N], nm, L[N], R[N];
int id = 0, h[N], logg[N], dep[N], f[N][25], rot[N], num[N];
struct node {
    int v, next;
}p[N];
void add(int u, int v) {
    id++;
    p[id].v = v;
    p[id].next = h[u];
    h[u] = id;
}
void init(int x, int fa) {//LCA预处理
    f[x][0] = fa, dep[x] = dep[fa] + 1;
    for(int i = 1; i <= logg[dep[x]]; i++)
        f[x][i] = f[f[x][i - 1]][i - 1];
    for(int i = h[x]; i; i = p[i].next)
        if(p[i].v != fa)
            init(p[i].v, x);
}
int lca(int x, int y) {//求LCA
    if(dep[x] < dep[y]) swap(x, y);
    while(dep[x] > dep[y]) x = f[x][logg[dep[x] - dep[y]] - 1];
    if(x == y) return x;
    for(int i = logg[dep[x]] - 1; i >= 0; i--)
        if(f[x][i] != f[y][i])
            x = f[x][i], y = f[y][i];
    return f[x][0];
}
int build(int l, int r) {//建树
    int x = ++tot;
    L[x] = l, R[x] = r;
    if(l == r) return x;
    int mid = (l + r) >> 1;
    ls[x] = build(l, mid);
    rs[x] = build(mid + 1, r);
    return x;
}
int clone(int x) {
    int t = ++tot;
    ls[t] = ls[x], rs[t] = rs[x];
    num[t] = num[x] + 1;
    L[t] = L[x], R[t] = R[x];
    return t;
}
int modify(int x, int l, int r, int v) {
    x = clone(x);
    if(l == r) return x;
    int mid = (l + r) >> 1;
    if(v <= mid) ls[x] = modify(ls[x], l, mid, v);
    else rs[x] = modify(rs[x], mid + 1, r, v);
    return x;
}
void dfs(int x) {
    int tmp = lower_bound(a + 1, a + nm + 1, b[x]) - a;//离散化
    rot[x] = modify(rot[f[x][0]], 1, nm, tmp);//根据父子关系建树
    for(int i = h[x]; i; i = p[i].next) {
        if(p[i].v == f[x][0]) continue;
        dfs(p[i].v);
    }
}
int query(int a1, int a2, int b1, int b2, int l, int r, int k) {//"a2-a1"，"b2-b1"分别表示两条链对应的树
    if(l == r) return l;
    int mid = (l + r) >> 1;
    int v = num[ls[a2]] - num[ls[a1]] + num[ls[b2]] - num[ls[b1]];
    if(v >= k) return query(ls[a1], ls[a2], ls[b1], ls[b2], l, mid, k);
    return query(rs[a1], rs[a2], rs[b1], rs[b2], mid + 1, r, k - v);
}
signed main() {
    cin >> n >> m;
    for(int i = 1; i <= n; i++) scanf("%lld", &a[i]), b[i] = a[i];
    for(int i = 1; i < n; i++) {
        int u, v; scanf("%lld%lld", &u, &v);
        add(u, v), add(v, u);
    }
    sort(a + 1, a + n + 1);
    nm = unique(a + 1, a + n + 1) - a - 1;//离散化
    rot[0] = build(1, nm);
    for(int i = 1; i <= n; i++)
        logg[i] = logg[i - 1] + (1 << logg[i - 1] == i);
    init(1, 0); dfs(1);
    while(m--) {
        int x, y, k; scanf("%lld%lld%lld", &x, &y, &k);
        x = x ^ la;
        int z = lca(x, y), fz = f[lca(x, y)][0];//询问的是点，要注意是否重或漏了LCA所在点
        int tmp = query(rot[fz], rot[x], rot[z], rot[y], 1, nm, k);
        la = a[tmp];
        printf("%lld\n", la);
    }
    return 0;
}

例三：子区间连续子串（节点存哈希）

给定一个序列，每次给出一组询问 l,r,b[1..k]，询问区间 [l,r] 中是否存在连续字串 b[1..k]。k 是固定的。

序列长度、询问个数 n,m\le 10^5，给定的 k\le 20。

如果要直接去尝试匹配，会十分的麻烦甚至于不可做。考虑 k 是固定的，可以将连续的 k 个数的哈希值计算出来作为一个新节点。

在新节点所构成的序列上建主席树，每次查询询问给出的 b[1..k] 的哈希值即可。注意位置的对应关系。

代码就是主席树板子加了一个哈希，就不放了。

例四：区间异或和（分块预处理）

给定一个序列，每次给出一组询问 l,r ，求区间 [l,r] 内的最大连续异或和，强制在线。

区间长度 n\le 12000，询问个数 m\le 6000，权值 a_i\le 10^9。

直接用可持久化01Trie去处理显然是不行的，因为无法快速确定一个值去放入01Trie查找使异或值最大。

观察数据范围，发现远小于一般 O(nlogn) 的题所给的数据范围，于是考虑分块。

预处理出 ans[i][r]，表示对于第 i 块的左端点 L_i 到 r 这个区间的答案。可以用可持久化01Trie辅助预处理。

预处理时，枚举每一个 i，从 L_i+1 开始从左到右枚举 r ，每枚举一个 r，用 a_r 在01Trie中查询异或最大值更新答案，并将其插入到01Trie中。枚举下一个块时，清空01Trie。

对于每一个询问区间 [l,r]，对于“整块”区间 [R[bl[l]]+1,r] 使用预处理出的答案。其中 bl[i] 表示 i 所在的块，R[i] 表示第 i 个块的右端点。

对于散块区间 [l,R[bl[l]]] 中每一个值，放入区间 [l,r]​ 所对应的01Trie中查询并更新答案。可以参考下图理解。

其中，[L,R] 表示询问区间，蓝色表示"整块"，利用预处理结果求解，绿色表示用01Trie求解的"散块"。

#include <bits/stdc++.h> 
#define int long long
#define ll int
using namespace std;
const int N = 1000010;
const int M = 31;
struct trie {
    int ch[N][2], tot;
    void clear() {
        tot = 0;
        memset(ch, 0, sizeof(ch));
    }
    void insert(int v) {
        int x = 0;
        for(ll i = M; i >= 0; i--) {
            int tmp = ((v & (1 << i)) ? 1 : 0);
            if(tmp) {
                if(!ch[x][1]) ch[x][1] = ++tot;
                x = ch[x][1];
            }
            else {
                if(!ch[x][0]) ch[x][0] = ++tot;
                x = ch[x][0];
            }
        }
    }
    int query(int v) {
        int res = 0, x = 0;
        for(ll i = M; i >= 0; i--) {
            int tmp = ((v & (1 << i)) ? 1 : 0);
            if(ch[x][!tmp]) res += (1 << i), x = ch[x][!tmp];
            else x = ch[x][tmp];
        }
        return res;
    }
}T;
int n, m, blk, bl[N], a[N], L[N], R[N], cnt;
int tot, num[N], ch[N][2], rot[N], s[N];
int ans[210][N], la = 0;
void insert(int x, int y, int v) {
    for(ll i = M; i >= 0; i--) {
        num[x] = num[y] + 1;
        int tmp = ((v & (1 << i)) ? 1 : 0);
        if(tmp) {
            if(!ch[x][1]) ch[x][1] = ++tot;
            ch[x][0] = ch[y][0];
            x = ch[x][1];
            y = ch[y][1];
        }
        else {
            if(!ch[x][0]) ch[x][0] = ++tot;
            ch[x][1] = ch[y][1];
            x = ch[x][0];
            y = ch[y][0];
        }
    }
    num[x] = num[y] + 1;
}
int query(int x, int y, int v) {
    int res = 0;
    for(ll i = M; i >= 0; i--) {
        int tmp = ((v & (1 << i)) ? 1 : 0);
        if(num[ch[x][!tmp]] - num[ch[y][!tmp]])
            res += (1 << i), x = ch[x][!tmp], y = ch[y][!tmp];
        else x = ch[x][tmp], y = ch[y][tmp];
    }
    return res;
}
signed main() {
    cin >> n >> m; blk = sqrt(n);
    int mod = n;
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for(int i = 1; i <= n; i++) s[i] = s[i - 1] ^ a[i];//前缀异或和
    for(int i = 1; i <= n; i++)
        bl[i] = (i - 1) / blk + 1;
    for(int i = 1; i <= n + 1; i++) {
        if(bl[i] != bl[i - 1]) {
            R[cnt] = i - 1;
            cnt++;
            L[cnt] = i;
        }
    }//分块预处理
    cnt--;
    for(int i = 1; i <= cnt; i++) {
        int p = R[i];
        ans[i][p] = a[p];
        T.clear();//清空
        T.insert(s[p]), T.insert(s[p - 1]);
        for(int j = p + 1; j <= n; j++) {
            ans[i][j] = max(ans[i][j - 1], T.query(s[j]));//预处理ans数组
            T.insert(s[j]);
        }
    }
    for(int i = 1; i <= n; i++)
        rot[i] = ++tot, insert(rot[i], rot[i - 1], s[i]);//正常在序列上建可持久化01Trie
    while(m--) {
        int x, y; scanf("%lld%lld", &x, &y);
        int l = min(((x + la) % mod) + 1, ((y + la) % mod) + 1);
        int r = max(((x + la) % mod) + 1, ((y + la) % mod) + 1);
        int p = R[bl[l]]; 
        int res = ans[bl[l]][r];//"整块"的答案
        for(int i = l - 1; i <= min(p - 1, r); i++)//计算"散块"的答案
            res = max(res, query(rot[r], rot[l - 2], s[i]));
        printf("%lld\n", res);
        la = res;
    }
    return 0;
}

注意此处说的"整块"和"散块"并非分块一般意义上的整块和散块，只是为方便描述而提出的概念。

例五：Persistent Bookcase（操作树）

维护一个二维零一矩阵（n,m \le 1000），支持四种操作（不超过 10^5 次）:

显然可以把矩阵展开成序列，操作一二就是正常的单点修改。对于操作三，看成区间取反打标记即可，操作四正常回退，询问正常做就行。

但是这里介绍另一种算法，操作树。至于为什么要把这东西放在可持久化，可能是它们能处理的东西有部分相似吧。

可以发现如果本题去除了操作四，按顺序去用 bitset 暴力做其它操作并更新每个时间的答案，是可做的且复杂度是正确的。

因为一共 q 次操作，复杂度最大的操作三也只需要 \frac{m}{w} 的复杂度，那总复杂度就是 O(\frac{mq}{w}) 的。

可以发现去除操作四后的求解可以看成一条链，每次从 i 走到 i+1 并更新答案，那我们就以此来建一棵树。

对于操作四外其他操作，连边 (i-1,i)，对于操作四，连边 (K,i)。最后 dfs 整棵树求解答案。

代码就不放了，原题是CF707D，可以去那里看。

总结一下操作树，这是一种离线做法，并且要满足可以很方便回溯才行。比如操作是区间加，就可以用区间减来回溯。

如果不能方便的回溯，就必须去记录整个状态，那空间就远远超过可持久化了，要是用动态开点，还不如直接写可持久化。

对比可持久化，优点：空间小、好理解、常熟小，缺点：必须离线、不能维护复杂状态。

例六：字符串移位

维护一个字符串，支持三种操作：

  1. 将区间 [l,r] 复制一遍加到 p 后面
  2. 将区间 [l,r] 删除
  3. 将区间 [l,r] 区间内的字母做恺撒位移，在字母表中向后移一位

可以用平衡树解决。发现第三个操作就是带取模的区间加，打标记即可，而第一个操作因为每次要复制 O(n) 个字符，会导致TLE。

考虑可持久化平衡树，发现其在用 split 将区间截出来时，已经相当于将其复制了一遍，直接加到 p 后即可。

操作二则是将区间 [1,l-1],[l,r],[r+1,n] 截出，合并 [1,l-1],[r+1,n] 即可。