指路学习笔记:可持久化线段树(主席树):静态 + 动态
先考虑如何求总序列第$k$小
我们可以建立一颗权值线段树,每个点存储的信息为该值域区间存在的数的个数。
因为线段树的性质,所以每个点的左子树的值域区间 $ <= $ 右子树的值域区间。
所以我们先看左子树区间有多少个数,记为$cnt_{left}$。
- 如果$k_i <= cnt_{left}$,说明第$k_i$小的数一定在左子树的值域内,所以问题便转换为了“在左子树的值域内找第$k_i$小的数”。
- 否则,说明第$k_i$小的数一定在左子树的值域内,考虑到左子树已经有$cnt_{left}$个最小的数,问题便转换为了“在右子树的值域内找第$k_i - cnt_{left}$小的数”
问题转换到任意区间
我们要用$[l_i, r_i]$ 区间的数建立权值线段树。
我们发现可以用前缀和来维护:
只要用预处理大法分别以$[1, l_i]$和$[1, r_i]$的数建立权值线段树,每个点的值对位相减即可。
关键性质
发现以$[1, x]$和$[1, x + 1]$区间内的数所建立的权值线段树的差异仅在一条链上:($A[x + 1]$的次数$+1$)。
也就是不超过$log_2n$个点。我们可以考虑动态开点:
- 与上一个权值线段树没有差异的地方直接指引过去
- 有差异,单独新增一个点
这样即可预处理出$[1, x] (1 <= x <= n)$所有的权值线段树了。
时间复杂度$O(nlog_2n)$,空间复杂度$O(2n + nlog_2n)$。
注意:由于值域很大,我们需要离散化一下。
参考代码:
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100005;
//d 为离散化数组
int n, m, len, a[N], d[N];
//T[i] 为 [1, i] 区间的权值线段树的根节点
int T[N], tot = 0;
//线段树的每个点
struct SegTree{
int l, r, v;
}t[N * 20];
//建树
int build(int l, int r){
int p = ++tot, mid = (l + r) >> 1;
if(l < r) {
t[p].l = build(l, mid);
t[p].r = build(mid + 1, r);
}
t[p].v = 0; return p;
}
//增加一个数 pre 为上一个的根节点。
int update(int pre, int l, int r, int v){
int p = ++tot, mid = (l + r) >> 1;
t[p].l = t[pre].l, t[p].r = t[pre].r, t[p].v = t[pre].v + 1;
if(l < r){
//应该更新哪一个值域区间
if(v <= mid) t[p].l = update(t[pre].l, l, mid, v);
else t[p].r = update(t[pre].r, mid + 1, r, v);
}
return p;
}
//查询
int query(int x, int y, int l, int r, int k){
//找到了
if(l == r) return l;
//对位相减
int sum = t[t[y].l].v - t[t[x].l].v, mid = (l + r) >> 1;
if(k <= sum) return query(t[x].l, t[y].l, l, mid, k);
else return query(t[x].r, t[y].r, mid + 1, r, k - sum);
}
int main(){
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
scanf("%d", a + i), d[i] = a[i];
//离散化
sort(d + 1, d + 1 + n);
len = unique(d + 1, d + 1 + n) - (d + 1);
for(int i = 1; i <= n; i++)
a[i] = lower_bound(d + 1, d + 1 + len, a[i]) - d;
T[0] = build(1, len);
for(int i = 1; i <= n; i++)
T[i] = update(T[i - 1], 1, len, a[i]);
//回答
while(m--){
int l, r, k; scanf("%d%d%d", &l, &r, &k);
int ans = query(T[l - 1], T[r], 1, len, k);
printf("%d\n", d[ans]);
}
return 0;
}
大佬。图下面有句话是错的
嗯
图咋没了 0..0
为什么不用build也能ac呢
因为确实没有初始内容…
啥叫没有初始内容,不太懂😥
初始化时相当于没有数,所以线段树上所有区间的个数都为0,相当于没有初始化
请问unique(d + 1, d + 1 + n) - (d + 1);
是什么意思
离散化
那那个-(d+1)代表什么
unique的用法,这样实际上会返回离散化后的长度
大佬,这题能否使用权值线段树+莫队算法求解?
这样的话时间复杂度就是 $O(N\sqrt{N}Log值域)$,离散化后值域变成 1e5,鉴于莫队是种神奇的算法所以有可能能跑过
果然T了 我之前用这种方法解决过区间不包含的情况,发现那种情况的复杂度小一些所以跑过了,感谢指导。