赞
踩
可持久化线段树,又称主席树。对于普通的线段树,想要支持回退操作(Undo)十分困难。可持久化线段树应时而生,可持久化线段树可以支持在不同版本直接进行穿梭,修改和查询。
以单点修改为例,对于一次单点修改创建一个新的版本,朴素的思路是将这个线段树从头到尾拷贝一份,但是拷贝操作不管是空间还是时间上的复杂度都是极高的。我们观察一下单点修改操作的修改过程。
我们把它变成圆形节点的形式:
其中,以橘色节点组成的路径即为修改路径,我们发现,只有修改路径上的节点的节点信息改变了,而其他节点的节点信息没有改变,这就是可持久化线段树的理论依据。
那么我们再创建新版本的时候,我们就可以只克隆修改路径上的节点,而不管其他节点。由于一条修改路径最多是 O ( log N ) O(\log N) O(logN),因此不会改变线段树的时间复杂度。
可持久化线段树最关键的操作为节点克隆。例如上图,我们创建新版本的线段树为:
由图发现,我们只需要克隆修改路径上的节点,并且每一个新节点(橘色节点)都会指向一个新节点和一个旧节点。并且,根节点永远都会被克隆。
因此,每一个新的根节点都是一颗可独立操作的线段树,虽然和其他版本公用了一些节点,那么每个根节点都代表了一个时间版本的线段树。
主席树最简单的应用为可持久化数组。即,可以访问任意一个版本下的数组元素,也可以对任意一个版本进行单点修改。
首先关于结构体的定义,在普通线段树的数据结构中,左右子节点的编号是可以通过根节点的编号算出来的。但是可持久化线段树却不具备这种完全二叉树的结构。因此,我们必须在结构体中存放孩子节点的编号信息。
struct Node
{
int l; // 左孩子节点编号
int r; // 右孩子节点编号
int val; // 权值
} t[100000000];
并且附带一个 t o t tot tot全局变量,记录节点编号的分配信息。
int tot = 0;
建树过程很简单,注意该函数返回节点的编号,并且是边建树边建边的过程。 a r r arr arr数组为原始数组。调用完该函数获得初始版本的线段树。
int buildTree(int l, int r)
{
int id = tot++; // 分配一个节点编号
if (l == r - 1) // 如果是叶子节点,那么直接赋值
{
t[id].val = arr[l];
}
else // 否则就要递归建树
{
int mid = (l + r) >> 1;
t[id].l = buildTree(l, mid);
t[id].r = buildTree(mid, r);
}
return id; // 返回该节点的编号s
}
克隆节点作为一个工具函数,其作用为克隆一个节点出来,且节点信息不改变。
int clone(int i)
{
int id = tot++;
t[id] = t[i];
return id;
}
单点修改时,修改路径上必须克隆出节点,并且递归修改,边修改边更改边的信息。
int update(int i, int l, int r, int idx, int val) { i = clone(i); // 修改路径上必须克隆出节点 if (l == r - 1) // 如果是叶子节点,那么就直接赋值即可 { t[i].val = val; } else // 不是则递归修改 { int mid = (l + r) >> 1; // 判断目标节点在左子树还是右子树,并将边指向新的克隆出来的节点 if (idx < mid) { t[i].l = update(t[i].l, l, mid, idx, val); } else { t[i].r = update(t[i].r, mid, r, idx, val); } } return i; // 返回节点编号 }
和普通的线段树没有区别。
int query(int i, int l, int r, int idx) { if (l == r - 1) // 目标节点,直接返回 { return t[i].val; } else // 递归查询 { int mid = (l + r) >> 1; if (idx < mid) { return query(t[i].l, l, mid, idx); } else { return query(t[i].r, mid, r, idx); } } }
可持久化线段树需要一个版本管理系统。其中 r o o t root root数组,存放了不同版本编号下的根节点。
h e a d head head为版本头指针,永远指向最新版本。
其中 r o o t [ i ] root[i] root[i]将返回第 i i i个版本的线段树头指针。
int main() { scanf("%d %d", &n, &m); for (int i = 1; i <= n; i++) { scanf("%d", arr + i); } int head = 0; // 版本头指针,永远指向最新版本 root[0] = buildTree(1, n + 1); // 初始版本 while (m--) { int vi, type; scanf("%d %d", &vi, &type); if (type == 1) { int idx, val; scanf("%d %d", &idx, &val); root[++head] = update(root[vi], 1, n + 1, idx, val); // 获得一个新版本 } else { int idx; scanf("%d", &idx); int ans = query(root[vi], 1, n + 1, idx); root[++head] = clone(root[vi]); // 获得一个新版本,虽然什么也没有修改 printf("%d\n", ans); } } return 0; }
最后给出完整代码。
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define FR freopen("in.txt", "r", stdin) #define FW freopen("out.txt", "w", stdout) struct Node { int l; // 左孩子节点编号 int r; // 右孩子节点编号 int val; // 权值 } t[100000000]; int arr[2000005]; int root[2000005]; int tot = 0; int n, m; int buildTree(int l, int r) { int id = tot++; // 分配一个节点编号 if (l == r - 1) // 如果是叶子节点,那么直接赋值 { t[id].val = arr[l]; } else // 否则就要递归建树 { int mid = (l + r) >> 1; t[id].l = buildTree(l, mid); t[id].r = buildTree(mid, r); } return id; // 返回该节点的编号s } int clone(int i) { int id = tot++; t[id] = t[i]; return id; } int update(int i, int l, int r, int idx, int val) { i = clone(i); // 修改路径上必须克隆出节点 if (l == r - 1) // 如果是叶子节点,那么就直接赋值即可 { t[i].val = val; } else // 不是则递归修改 { int mid = (l + r) >> 1; // 判断目标节点在左子树还是右子树,并将边指向新的克隆出来的节点 if (idx < mid) { t[i].l = update(t[i].l, l, mid, idx, val); } else { t[i].r = update(t[i].r, mid, r, idx, val); } } return i; // 返回节点编号 } int query(int i, int l, int r, int idx) { if (l == r - 1) // 目标节点,直接返回 { return t[i].val; } else // 递归查询 { int mid = (l + r) >> 1; if (idx < mid) { return query(t[i].l, l, mid, idx); } else { return query(t[i].r, mid, r, idx); } } } int main() { scanf("%d %d", &n, &m); for (int i = 1; i <= n; i++) { scanf("%d", arr + i); } int head = 0; // 版本头指针,永远指向最新版本 root[0] = buildTree(1, n + 1); // 初始版本 while (m--) { int vi, type; scanf("%d %d", &vi, &type); if (type == 1) { int idx, val; scanf("%d %d", &idx, &val); root[++head] = update(root[vi], 1, n + 1, idx, val); // 获得一个新版本 } else { int idx; scanf("%d", &idx); int ans = query(root[vi], 1, n + 1, idx); root[++head] = clone(root[vi]); // 获得一个新版本,虽然什么也没有修改 printf("%d\n", ans); } } return 0; }
有了可持久化数组,基于数组的数据结构都有了可持久化的版本,例如可持久化并查集,可持久化链表。
有时候,我们构造线段树的时候并不需要把所有的线段树的节点都构造出来,我们可以在有必要使用这个节点时候才去构造节点,过程类似于主席树。这样,可以减少线段树带来的空间问题。
百分之90的动态开点线段树都可以进行离散化+普通线段树。
思路应用了前缀和思想,首先对数据进行离散化,维护离散序号区间 [ 1 , i d ] [1,id] [1,id]注意去重,每个槽就储存了该标号数字的个数,从数组从左到右进行插入,每次插入都创建一个新的线段树版本。
假如查询区间 [ l , r ] [l,r] [l,r]那么对应每一个节点 i d id id,用 r r r的版本减去 l − 1 l - 1 l−1版本的数量即可得到该区间下的的数量。
然后根据区间内数字的数量选择左右子树即可。
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define FR freopen("in.txt", "r", stdin) #define FW freopen("out.txt", "w", stdout) struct Node { int l; int r; int val; } t[5000005]; int root[200005]; int tot = 0; int head = 0; int buildTree(int l, int r) { int id = tot++; if (l == r - 1) { t[id].val = 0; } else { int mid = (l + r) >> 1; t[id].l = buildTree(l, mid); t[id].r = buildTree(mid, r); t[id].val = 0; } return id; } int clone(int i) { int id = tot++; t[id] = t[i]; return id; } int insert(int i, int l, int r, int idx) { i = clone(i); if (l == r - 1) { t[i].val++; } else { t[i].val++; int mid = (l + r) >> 1; if (idx < mid) { t[i].l = insert(t[i].l, l, mid, idx); } else { t[i].r = insert(t[i].r, mid, r, idx); } } return i; } int getKth(int a, int b, int l, int r, int k) { if (l == r - 1) { return l; } else { int mid = (l + r) >> 1; int ln = t[t[b].l].val - t[t[a].l].val; int rn = t[t[b].r].val - t[t[a].r].val; if (ln >= k) { return getKth(t[a].l, t[b].l, l, mid, k); } else { return getKth(t[a].r, t[b].r, mid, r, k - ln); } } } int ori[200005]; int n, m; int main() { scanf("%d %d", &n, &m); set<int> st; for (int i = 1; i <= n; i++) { scanf("%d", ori + i); st.insert(ori[i]); } int id = 0; map<int, int> mp, vmp; for (auto it = st.begin(); it != st.end(); it++) { id++; mp[id] = *it; vmp[*it] = id; } root[0] = buildTree(1, id + 1); for (int i = 1; i <= n; i++) { root[i] = insert(root[i - 1], 1, id + 1, vmp[ori[i]]); } while (m--) { int l, r, k; scanf("%d %d %d", &l, &r, &k); int val = getKth(root[l - 1], root[r], 1, id + 1, k); printf("%d\n", mp[val]); } return 0; }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。