主席树(可持久化线段树) 模板题
优秀题解 【学习笔记】主席树
标准的线段树模板题请参考 AcWing 1275. 最大数
"可持久化线段树" 在本题目的作用实际上是指"使用多个入口指针保存多个不同版本的线段树",
类似Git, 每个版本包含当前版本和之前的所有内容: 每新增一个点都建一颗新树,
复制前一棵树并插入新元素所造成的修改.
实现上, 是在build的时候只建立树的骨架而不保存元素, 而对每一个点都做一次insert,
在插入新点的同时, 复制上一棵树, 再插入新点
主席数的整体定义
与线段树不同的是,树节点维护的$l$,$r$值从区间的端点值变成左右子节点(标志值),那么我们下面用几张图来说明主席数的执行流程。
首先先初始化一棵空的树
注意这里区间的定义不用真的在主席数的树节点结构上表现出来,
而是在递归的时候规定递归哪个区间,然后用树节点的标志值来表示他这个节点所代表的区间是什么。
用cnt来表示它这个区间插入了多少个数
下面用加入一段序列来进行举例:序列4 3 2 3 6 1
区间[1,1]的线段树(蓝色节点为新节点)
当我们插入一个元素的时候,我们其实只需要修改其中一条链的数据,对于其他剩余的节点我们就直接复制,同时复制旧版本的节点到新的树上,复制完后新版本的节点加上新的版本号
下面的执行步骤同理
区间[1,2]的线段树(橙色节点为新节点)
区间[1,3]的线段树(紫色节点为新节点)
int insert(int p, int l, int r, int x)
{
// 假设现在是从外界第一次执行insert, 那么调用的时候, p必定是根节点,
// 那么q就相当于复制了一个根节点, 从节点q进入这棵树的时候, 也能得到之前的所有内容.
// 同理, 再往下二分递归的时候, insert会继续复制根节点的左(右)子树, 一直递归直到l==r之前,
// q和原来的p都是一毛一样. 直到l==r才真正插入了新点, 每次插入的时间空间复杂度都是lgk,
// 总加起来就是lg1+lg2+...+lgn = lg(n!), 根据stirling公式, 结果为nlgn (大O)
int q = ++idx;
tr[q] = tr[p];
if (l == r) // 如果区间长度为1, 说明就是放这里了
{
// tr[q].cnt++是表示插在这个叶节点上
// 这个线段树只是保存的每个区间里面的元素个数
// 每次插入都只是覆盖到的那堆区间里面的cnt发生+1
tr[q].cnt++;
return q;
}
int mid = l + r >> 1;
if (x <= mid) tr[q].l = insert(tr[p].l, l, mid, x);
else tr[q].r = insert(tr[p].r, mid+1, r, x);
tr[q].cnt = tr[tr[q].l].cnt + tr[tr[q].r].cnt; // 相当于pushup了
return q;
}
回到本题,
我们发现需要进行离散化,因为此时建树的依据是数值的大小,左子树存放的数比右子数的存放的数要小,而不是下标,又因为原本的数据取值太大,因此需要通过离散化将所有数据离散为一个较小范围,离散后我们并不在意它们的真实值,只需要某个数在所有数中的位置,通过位置可以找到在原数据中的真实值。
离散化的模板可以参考 AcWing 802. 区间和
主席树
c++代码
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
const int N = 100010;
using namespace std;
struct Node{
int l,r; //分别表示左右节点
int cnt; //表示当前树节点插入了多少个数
}tr[N * 4 + N * 17]; //初始骨架N * 4 再加上最多M次插入一共修改MlogM个节点
vector<int> nums; //用于离散化的数组,由于数的范围很大,但是不能开那么大的空间,所以需要离散化
int root[N],idx; //root记录根节点的版本号【root[r]表示插入了第r个数版本的线段树】, idx记录树节点的版本号
int a[N]; //原始数组
int n,m;
int find(int x){
int idx = lower_bound(nums.begin(),nums.end(),x) - nums.begin();
return idx;
}
int build(int l,int r){ //返回标志值
int p = idx++;
if(l == r){ //到叶子节点了
return p;
}
int mid = l + r >> 1;
//递归到最底层之后向上给父节点的属性赋值
tr[p].l = build(l,mid); tr[p].r = build(mid + 1,r);
return p;
}
// l, r是要放入的坐标范围, x是要插入的数离散化后的位置
int insert(int p,int l,int r,int x){ //返回值是新版本树节点的标志值
int q = idx++;
tr[q] = tr[p]; //先将上一个版本信息复制过来
if(l == r){ //遍历到叶子节点,同时找到了要插入的位置,cnt++
tr[q].cnt++;
return q;
}
//接着找要插入的位置
int mid = l + r >> 1;
//这里也是新版本树节点直接复制旧版本树的信息,同时返回一个新的版本号
//下表小于mid放左区间,反之放右区间
if(x <= mid) tr[q].l = insert(tr[p].l,l,mid,x);
else tr[q].r = insert(tr[p].r,mid + 1, r ,x);
tr[q].cnt = tr[tr[q].l].cnt + tr[tr[q].r].cnt; // 相当于pushup了
return q;
}
// l ,r是检索范围, q是当前第r个节点root[r]能包含1~r之间所有
// q的输入是root[r],p的输入是root[l-1], 作用是剔除这个根节点所包含数据的影响(前缀和的思想)
int query(int q, int p, int l, int r, int k){
//遍历到了叶子节点的位置,说明找到了所需要的位置
if(l == r) return r;
// 目标是求l r之间的第k小
// tr[tr[q].l].cnt - tr[tr[p].l].cnt的结果是求出在p之后插入到q这些数之后,
// 有多少个数(cnt)插入了p的左子树, 由于p的内容肯定不能出现在l r之间(p根节点就是root[l-1]),
// 所以cnt就是相当于"存在于r版本左子树中的数但不存在于l - 1版本左子树中的数的个数"
int cnt = tr[tr[q].l].cnt - tr[tr[p].l].cnt;
int mid = l + r >> 1;
// k <= cnt说明要找的元素在q的左子树里面, 同时这里面也要剔除掉包含在p左子树的内容
if (k <= cnt) return query(tr[q].l, tr[p].l, l, mid, k);
else return query(tr[q].r, tr[p].r, mid+1, r, k - cnt); // 类似同上
}
int main(){
scanf("%d%d",&n,&m);
for(int i = 1;i <= n;++i){
scanf("%d",&a[i]);
nums.push_back(a[i]);
}
//离散化
sort(nums.begin(),nums.end());
nums.erase(unique(nums.begin(),nums.end()),nums.end());
root[0] = build(0,nums.size() - 1); //初始时,建立一个空的骨架,不同版本的线段树的结构都是一样的
for(int i = 1;i <= n;++i){
//初始
root[i] = insert(root[i - 1],0,nums.size() - 1,find((a[i])));
}
while(m--){
int l,r,k;
scanf("%d%d%d",&l,&r,&k);
//查询[l,r]区间中的第k大数,利用前缀和的思想,从[l ~ r]中的数据剔除掉[1 ~ l-1]的数据,
//不同版本的线段树的结构都是一样的,所以初始都是从0到nums.size()这个范围当中找
printf("%d\n",nums[query(root[r],root[l - 1],0,nums.size() - 1,k)]);
}
return 0;
}
画图终于看懂了
%%%好详细
蟹蟹佬,终于看懂了 Orz
tql
tql
好的解析!