题解 P3834 【【模板】可持久化线段树 1(主席树)】
Ireliaღ
2019-08-18 15:37:19
**这里提供两个非主席树,没有其他题解提到,但是复杂度正确,或许比主席树写起来更容易的做法**
## 从原理开始
我们想要求区间第$k$小,需要用一种可持久化数据结构,版本$i$维护从$a_1$到$a_i$所有数的出现次数,这样来求出区间第$k$小。那么,“这种”数据结构需要满足哪些性质?
1. 资瓷可持久化(废话,题目在那)
2. 资瓷查询全局第$k$小(显然)
3. **不同版本树的形态相似**(为性质$4$提供条件)
4. **可以从两个版本的树根开始同时在树上走路,并在“相同地位”的节点上对$size$进行作差,来得到指定区间内的信息。**(重点!)
那么,我们~~很容易~~根据以上性质想到以下数据结构
* 值域线段树(标准主席树做法)
* 二叉搜索树(可以看普通平衡树P3369)
* 0-1字典树(普通平衡树P3369中有几篇题解)
* Leafy Search Tree(也有人叫它Finger Tree,但好像是个~~美丽的~~误会,按照原理完全可以实现,但是我太菜没写明白)
## 本题解法
可持久化值域线段树(主席树)做法很多题解都写了,这里不再多讲。重点讲下面的两种做法。
### 可持久化二叉搜索树
因为二叉搜索树满足**中序遍历即有序序列**的性质,所以我们可以使用可持久化BST来解决静态区间第$k$小的问题,只需要在递归不同版本的“相同地位”节点时,对两个$size$作差即可。
代码如下
```cpp
// luogu-judger-enable-o2
// luogu-judger-enable-o2
#include <iostream>
using std::cin;
using std::cout;
const int MAXN = 2e5 + 5;
int n, m;
int a[MAXN];
struct Node{
int val, cnt, siz;
Node *ch[2];
Node() {}
Node(int val) : val(val) {
cnt = 1;
siz = 1;
ch[0] = ch[1] = NULL;
}
}pool[MAXN << 5];
int ncnt = 0;
Node *NewNode(int val) {
pool[ncnt] = Node(val);
return &pool[ncnt++];
}
Node *NewNode(void) {
return &pool[ncnt++];
}
Node *rt[MAXN];
void Update(Node *now) {
now->siz = now->cnt + (now->ch[0] ? now->ch[0]->siz : 0) + (now->ch[1] ? now->ch[1]->siz : 0);
}
Node *Copy(Node *now) {
Node *ret = NewNode();
*ret = *now;
return ret;
}
void Insert(Node *&now, int k) {
if (!now) {
now = NewNode(k);
return;
}
now = Copy(now);
if (k < now->val) Insert(now->ch[0], k);
else if (k == now->val) now->cnt++;
else Insert(now->ch[1], k);
Update(now);
}
int Kth(Node *now1, Node *now2, int k) {
int ls1 = ((now1 && now1->ch[0]) ? now1->ch[0]->siz : 0);
int ls2 = ((now2 && now2->ch[0]) ? now2->ch[0]->siz : 0);
int ls = ls2 - ls1;
int ncnt = (now2 ? now2->cnt : 0) - (now1 ? now1->cnt : 0);
if (k <= ls) return Kth((now1 ? now1->ch[0] : NULL), (now2 ? now2->ch[0] : NULL), k);
else if (k <= ls + ncnt) return now2->val;
else return Kth((now1 ? now1->ch[1] : NULL), (now2 ? now2->ch[1] : NULL), k - ls - ncnt);
}
void Init() {
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> a[i];
}
void Work() {
for (int i = 1; i <= n; i++) {
rt[i] = rt[i - 1];
Insert(rt[i], a[i]);
}
int x, y, k;
for (int i = 1; i <= m; i++) {
cin >> x >> y >> k;
cout << Kth(rt[x - 1], rt[y], k) << "\n";
}
}
int main() {
std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
Init();
Work();
return 0;
}
```
虽然这份代码可以切掉本题,~~并且跑的比很多主席树要快得多~~,但是由于我们需要满足性质$3$,无法对BST做出平衡措施,所以**出题人可以通过恶意构造单调增/减的序列把可持久化BST的时间和空间卡成$n^2$**。
然而,介于绝大多数人求静态区间第$k$小都用主席树,出题人很难想到卡BST,所以我到现在没因为使用BST代替主席树翻车过。
时间复杂度单次查询$O(log(n))$,预处理$O(nlog(n))$(非恶意数据)
### 可持久化0-1字典树
0-1字典树,顾名思义,把二进制数当做字符串存入字典树中,这样通过维护节点的$size$,可以求出全局第$k$小,**并且跑的比绝大多数平衡树都要快**。这样,性质已经满足,我们可以通过可持久化来求出区间第$k$小。
代码如下
```cpp
// luogu-judger-enable-o2
#include <iostream>
using std::cin;
using std::cout;
typedef unsigned int U;
const int MAXN = 2e5 + 5;
int n, m;
int a[MAXN];
struct Node{
int siz;
Node *ch[2];
}pool[MAXN << 6];
Node *NewNode() {
static int cnt = 0;
pool[cnt].siz = 0;
pool[cnt].ch[0] = NULL;
pool[cnt].ch[1] = NULL;
return &pool[cnt++];
}
Node *rt[MAXN];
void Update(Node *now) {
now->siz = (now->ch[0] ? now->ch[0]->siz : 0) + (now->ch[1] ? now->ch[1]->siz : 0);
}
Node *Copy(Node *now) {
Node *ret = NewNode();
*ret = *now;
return ret;
}
void Insert(Node *&now, U num, int base) {//base为父边的数位
if (!now) now = NewNode();
else now = Copy(now);
if (base == 0) {
now->siz++;
return;
}
int f = (num & (1U << base - 1)) ? 1 : 0;
Insert(now->ch[f], num, base - 1);
Update(now);
}
U Kth(Node *now1, Node *now2, int k, U num, int base) {//num为收集下来的数字
if (base == 0) return num;
int ls1 = ((now1 && now1->ch[0]) ? now1->ch[0]->siz : 0);
int ls2 = ((now2 && now2->ch[0]) ? now2->ch[0]->siz : 0);
int ls = ls2 - ls1;
if (k <= ls) return Kth(now1 ? now1->ch[0] : NULL, now2 ? now2->ch[0] : NULL, k, num, base - 1);
else return Kth(now1 ? now1->ch[1] : NULL, now2 ? now2->ch[1] : NULL, k - ls, num + (1U << base - 1), base - 1);
}
void Init() {
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> a[i];
}
void Work() {
rt[0] = new Node();
for (int i = 1; i <= n; i++) {
rt[i] = rt[i - 1];
Insert(rt[i], a[i], 32);
}
int x, y, k;
for (int i = 1; i <= m; i++) {
cin >> x >> y >> k;
cout << Kth(rt[x - 1], rt[y], k, 0, 32) << "\n";
}
}
int main() {
std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
Init();
Work();
return 0;
}
```
时间复杂度稳定每次$O(log(maxnum))$,预处理$O(nlog(maxnum))$
这里我比较推荐利用可持久化Trie来解决静态区间第$k$小以及类似问题,因为Trie的复杂度最优,并且可以解决最大异或和等其他问题。