概述
这篇文章是我对学习主席树的一个小结。
当然，笔者很菜，除了模板就什么都不会打，也会有一些知识理解得不够深刻。
因此，这篇文章以后还会不定期更新的。
主席树
主席树，全名称为可持久化线段树，也就是把每个阶段的线段树保存起来，每次可以直接访问一个阶段的状态，是神犇(HJT)发明出来的一种数据结构。
先放出一个经典模板题：静态区间第(k)小。
题目描述
如题，给定(N)个整数构成的序列，将对于指定的闭区间查询其区间内的第K小值。
输入输出格式
输入格式
第一行包含两个正整数(N)、(M)，分别表示序列的长度和查询的个数。
第二行包含(N)个整数，表示这个序列各项的数字。
接下来(M)行每行包含三个整数(l, r, k) , 表示查询区间([l, r])内的第(k)小值。
输出格式
输出包含(k)行，每行(1)个整数，依次表示每一次查询的结果
输入输出样例
输入样例#1
5 5
25957 6405 15770 26287 26465
2 2 1
3 4 1
4 5 1
1 2 2
4 4 1
输出样例#1
6405
15770
26287
25957
26287
说明
数据范围
对于(20\%)的数据满足：(1 leq N, M leq 10)
对于(50\%)的数据满足：(1 leq N, M leq 10^3)
对于(80\%)的数据满足：(1 leq N, M leq 10^5)
对于(100\%)的数据满足：(1 leq N, M leq 2cdot 10^5)
对于数列中的所有数(a_i)，均满足(-{10}^9 leq a_i leq {10}^9)
样例数据说明
(N=5)，数列长度为(5)，数列从第一项开始依次为([25957, 6405, 15770, 26287, 26465 ])
第一次查询为([2, 2])区间内的第一小值，即为(6405)
第二次查询为([3, 4])区间内的第一小值，即为(15770)
第三次查询为([4, 5])区间内的第一小值，即为(26287)
第四次查询为([1, 2])区间内的第二小值，即为(25957)
第五次查询为([4, 4])区间内的第一小值，即为(26287)
题解
经典的主席树题。
由于本题中的(a_i)数据范围很大，因此我们需要将数据进行离散化处理。
然后就开始执行主席树的操作。
先来看看插入操作的代码：
void add(int &num, int &x, int l, int r)
{
T[cnt++] = T[x], x = cnt - 1, ++T[x].sum;
if (l == r) return;
int mid = (l + r) >> 1;
if (num <= mid) add(num, T[x].L, l, mid);
else add(num, T[x].R, mid + 1, r);
}
和线段树很相似，不是吗？(主席树不就是可持久化的线段树吗)
接着看寻找答案的代码：
int getans(int i, int j, int k, int l, int r)
{
if (l == r) return l;
int t = T[T[j].L].sum - T[T[i].L].sum, mid = (r + l) >> 1;
if (k <= t) return getans(T[i].L, T[j].L, k, l, mid);
else return getans(T[i].R, T[j].R, k - t, mid + 1, r);
}
和线段树的思想一样，分开去找左右两子树。
代码就这么一点儿，并不难记。
不难得出最后的代码：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cctype>
#include <vector>
#include <set>
#include <map>
#include <string>
using namespace std;
inline int gi()
{
int f = 1, x = 0; char c = getchar();
while (c < '0' || c > '9') { if (c == '-')f = -1; c = getchar();}
while (c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar();}
return f * x;
}
struct Node
{
int L, R, sum;
} T[4000003];
struct lisan
{
int x, idx;
bool operator < (const lisan &rhs) const
{
return x < rhs.x;
}
} a[4000003];
int r[2000003], t[2000003], n, m, cnt;
void add(int &num, int &x, int l, int r)
{
T[cnt++] = T[x], x = cnt - 1, ++T[x].sum;
if (l == r) return;
int mid = (l + r) >> 1;
if (num <= mid) add(num, T[x].L, l, mid);
else add(num, T[x].R, mid + 1, r);
}
int getans(int i, int j, int k, int l, int r)
{
if (l == r) return l;
int t = T[T[j].L].sum - T[T[i].L].sum, mid = (r + l) >> 1;
if (k <= t) return getans(T[i].L, T[j].L, k, l, mid);
else return getans(T[i].R, T[j].R, k - t, mid + 1, r);
}
int main()
{
n = gi(), m = gi();
for (int i = 1; i <= n; i++)
{
a[i].x = gi(), a[i].idx = i;
}
sort(a + 1, a + n + 1);//离散化
for (int i = 1; i <= n; i++) r[a[i].idx] = i;
cnt = 1;
for (int i = 1; i <= n; i++)
{
t[i] = t[i - 1], add(r[i], t[i], 1, n);//建树
}
while (m--)
{
int x = gi(), y = gi(), z = gi();
printf("%d
", a[getans(t[x - 1], t[y], z, 1, n)].x);//输出答案
}
return 0;
}
可持久化数组
可持久化数组属于主席树的一种变形，它是带修改的。
即：可持久化数组是一种支持单点修改、单点查询的可持久化数据结构。
我怎么感觉可持久化数组比主席树还简单啊
还是来边看代码边理解思路：
定义一个结构体，存储每个节点的信息：左儿子、右儿子、权值。
struct Node
{
int l, r, id;
} q[20000005];
新建一个节点：
inline int newnode(int x)
{
q[++tot] = q[x];
return tot;
}
来看建树的代码(其实就是新建节点的过程):
int jianshu(int node, int beg, int en)
{
node = ++tot;
if (beg == en)
{
q[node].id = a[beg];
return tot;
}
int mid = (beg + en) >> 1;
q[node].l = jianshu(q[node].l, beg, mid);//左儿子
q[node].r = jianshu(q[node].r, mid + 1, en);//右儿子
return node;
}
更新数值：
int modify(int node, int beg, int en, int x, int y)
{
node = newnode(node);//新建一个节点
if (beg == en)
q[node].id = y;//更新完了
else
{
int mid = (beg + en) >> 1;
if (x <= mid)
q[node].l = modify(q[node].l, beg, mid, x, y);//更新左子树
else
q[node].r = modify(q[node].r, mid + 1, en, x, y);//更新右子树
}
return node;
}
寻找答案：
int getans(int node, int beg, int en, int x)
{
if (beg == en)
return q[node].id;//已经找到答案了
else
{
int mid = (beg + en) >> 1;
if (x <= mid)
return getans(q[node].l, beg, mid, x);//向左寻找
else
return getans(q[node].r, mid + 1, en, x);//向右寻找
}
}
不难得出全部代码：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cctype>
using namespace std;
inline int gi()
{
int f = 1, x = 0;
char c = getchar();
while (c < '0' || c > '9')
{
if (c == '-')
f = -1;
c = getchar();
}
while (c >= '0' && c <= '9')
{
x = x * 10 + c - '0';
c = getchar();
}
return f * x;
}
int n, m, ans, a[1000005], tot, root[1000005];
struct Node
{
int l, r, id;
} q[20000005];
inline int newnode(int x)
{
q[++tot] = q[x];
return tot;
}
int jianshu(int node, int beg, int en)
{
node = ++tot;
if (beg == en)
{
q[node].id = a[beg];
return tot;
}
int mid = (beg + en) >> 1;
q[node].l = jianshu(q[node].l, beg, mid);
q[node].r = jianshu(q[node].r, mid + 1, en);
return node;
}
int modify(int node, int beg, int en, int x, int y)
{
node = newnode(node);
if (beg == en)
q[node].id = y;
else
{
int mid = (beg + en) >> 1;
if (x <= mid)
q[node].l = modify(q[node].l, beg, mid, x, y);
else
q[node].r = modify(q[node].r, mid + 1, en, x, y);
}
return node;
}
int getans(int node, int beg, int en, int x)
{
if (beg == en)
return q[node].id;
else
{
int mid = (beg + en) >> 1;
if (x <= mid)
return getans(q[node].l, beg, mid, x);
else
return getans(q[node].r, mid + 1, en, x);
}
}
int main()
{
n = gi(), m = gi();
for (int i = 1; i <= n; i++)
a[i] = gi();
root[0] = jianshu(0, 1, n);//建树
for (int i = 1; i <= m; i++)
{
int rf = gi(), fl = gi(), x = gi();
if (fl == 1)
{
int y = gi();
root[i] = modify(root[rf], 1, n, x, y);//保存状态+修改
}
else
{
printf("%d
", getans(root[rf], 1, n, x));//输出答案
root[i] = root[rf];//保存状态
}
}
return 0;
}
总结
主席树和可持久化数组的代码很短，但是，理解思路才是最重要的，它们的思想也很重要。