动态开点线段树

常规写法的线段树只能维护不算很长的数组,由于空间不够,对于 $10^9$ 级别的数组却不能很好地维护。所以,我们要用到动态开点线段树。

核心思想:节点只有在有需要的时候才被创建

比如说,要求在一个长度为 $n < 10^9$ 的数组上实现区间求和、单点修改的操作,初始数组元素值均为 0。

那么,我们一开始只创建一个根结点,接下来遵循动态开点的核心思想进行操作。

比如下面这张图的例子,我们依次修改 1, 2, 8 三个结点,途中创建了必要的结点。而在图中没有显示的空结点并没有被创建,视为 0,这样就节省了空间。

dynamic

那么对于区间修改时,会有 pushdown() 操作,可能会修改一个不存在的结点。这时有两个解决方案:

  1. pushdown() 时,如果缺少孩子,就直接创建一个新的孩子就可以了。
  2. 使用 标记永久化 技巧(李超线段树),让结点不再进行 pushdown(),进一步节省了空间。

复杂度分析:单次操作的时间复杂度是不变的,为 $O(\log n)$。对于空间复杂度,由于每次操作都有可能创建并访问全新的一系列结点,因此 $m$ 次操作的空间复杂度是 $O(m\log n)$,不再是原本线段树的 $O(n)$。

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int n, cnt, root;  // cnt 表示当前结点个数
int sum[N*2], ls[N*2], rs[N*2];
void upd(int& rt, int l, int r, int p, int f) { // 注意这里传入一个引用,可以修改 ls 或 rs 数组
  if (!rt) rt = ++cnt;  // 当结点为空时,创建一个新的结点
  if (l == r) {
    sum[rt] += f;
    return;
  }  
  int m = (l + r) >> 1;
  if (p <= m)
    upd(ls[rt], l, m, p, f);
  else
    upd(rs[rt], m + 1, r, p, f);
  sum[rt] = sum[ls[rt]] + sum[rs[rt]];  // pushup
}
int query(int rt, int l, int r, int L, int R) {
  if (!rt) return 0;  // 如果结点为空,返回 0
  if (l >= L && r <= R) return sum[rt];
  int m = (l + r) >> 1, ans = 0;
  if (L <= m)
    ans += query(ls[rt], l, m, L, R);
  if (R > m)
    ans += query(rs[rt], m + 1, r, L, R);
  return ans;
}

可持久化线段树

可持久化线段树,就是可以存储历史信息的线段树。

比如我们对数组进行了 n 次修改,然后突然希望回到第 i 个版本,然后又基于这个版本进行一些新的修改等,就是可持久化线段树需要解决的问题。

最暴力的想法是,对于每一次修改,都重新建一棵完整的线段树。然后,空间爆炸了。

persistent-seg

我们分析一下,就会发现每一次修改时,改变的结点的个数都是线段树的深度 $\log n$。如图,我们修改了结点 $8$ 的值,受到影响的结点都在从根结点 $1$ 到 $8$ 的路径上,即 $1, 2, 4, 8$。其他的结点都是不变的。因此,我们只需要重新创建有改动的结点即可,例如 $1(new), 2(new), 4(new), 8(new)$(新的结点是动态开点的,编号和原来的不一样,因此这里用 $(new)$ 标注)。然后,例如对于新的根结点 $1(new)$,将左儿子指向新的 $2(new)$,右儿子和旧的根结点 $1(old)$ 的右儿子相同,是 $3(old)$,不用修改

例题

Luogu-P3919 【模板】可持久化线段树 1(可持久化数组)

如题,你需要维护这样的一个长度为 $ N $ 的数组,支持如下几种操作

  1. 在某个历史版本上修改某一个位置上的值
  2. 访问某个历史版本上的某一位置的值

此外,每进行一次操作(对于操作2,即为生成一个完全一样的版本,不作任何改动),就会生成一个新的版本。版本编号即为当前操作的编号(从1开始编号,版本0表示初始状态数组)

$ 1 \leq N, M \leq {10}^6, 1 \leq {loc}_i \leq N, 0 \leq v_i < i, -{10}^9 \leq a_i, {value}_i \leq {10}^9$

程序实现

为了保险,线段树数组的大小应设为 n << 5洛谷上关于此的讨论

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000006;
int n, m;
int a[MAXN];
int rt[MAXN << 5], lc[MAXN << 5], rc[MAXN << 5], sm[MAXN << 5], ver = 0, tot = 0;
void build(int& rt, int l, int r) {
  rt = ++tot;
  if (l == r) {
    sm[rt] = a[l];
    return;
  }
  int m = (l + r) >> 1;
  build(lc[rt], l, m);
  build(rc[rt], m + 1, r);
}
void update(int& rt, int pre, int l, int r, int q, int v) {  // pre:原结点
  rt = ++tot;
  lc[rt] = lc[pre];
  rc[rt] = rc[pre];
  sm[rt] = sm[pre];  // 复制原结点的信息,之后按需修改
  if (l == r) {
    sm[rt] = v;
    return;
  }
  int m = (l + r) >> 1;
  if (q <= m)
    update(lc[rt], lc[pre], l, m, q, v);  // 新建左子结点,但是右子结点不变
  else
    update(rc[rt], rc[pre], m + 1, r, q, v);  // 反之
}
int query(int rt, int l, int r, int q) {
  if (l == r) return sm[rt];
  int m = (l + r) >> 1;
  if (q <= m) return query(lc[rt], l, m, q);
  return query(rc[rt], m + 1, r, q);
}
int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; i++) cin >> a[i];
  build(rt[0], 1, n);
  while (m--) {
    int v, opt, loc, val;
    cin >> v >> opt >> loc;
    if (opt == 1) {
      cin >> val;
      update(rt[++ver], rt[v], 1, n, loc, val);  // rt[++ver] 以 rt[v] 为基础
    } else {
      cout << query(rt[v], 1, n, loc) << endl;
      rt[++ver] = rt[v];
    }
  }
  return 0;
}

权值线段树

普通的线段树维护的是区间内最值或总和,而权值线段树每个结点维护的是在一个区间内的数出现的次数。因此,可以把权值线段树看作一个桶。举个例子,如果 $tree[1]$ 对应的区间是 $[1, 8]$,那么它的值就是 $1, 2, \cdots, 7, 8$ 在原数组中出现的次数之和

权值线段树中,采用元素到下标数组映射的方式进行插入。当数据离散程度较大的情况,空间的利用效率比较低,这时候可以搭配离散化技巧(下面有例子)。

一个常见的应用是把权值线段树用于处理区间第 $K$ 小/大问题。

例题:Luogu-P1138 第 k 小整数 RECORD

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <algorithm>
#include <cstdio>
#include <iostream>
using namespace std;
const int MAXN = 10005;
int n, k, a[MAXN];
int tree[MAXN << 1], lc[MAXN << 1], rc[MAXN << 1], root = 0, tot = 0;
// 对于权值线段树来说,build 函数是没有必要的,因为默认值为 0
// 只不过这里为了节省空间用了动态开点,才需要 build()
void build(int &rt, int l, int r) { 
  rt = ++tot;
  if (l == r) return;
  int m = (l + r) >> 1;
  build(lc[rt], l, m);
  build(rc[rt], m + 1, r);
}
void update(int rt, int l, int r, int q) {
  if (l == r) {
    tree[rt] = 1; // 出现了 1 次
    return;
  }
  int m = (l + r) >> 1;
  if (q <= m)
    update(lc[rt], l, m, q);
  else
    update(rc[rt], m + 1, r, q);
  tree[rt] = tree[lc[rt]] + tree[rc[rt]]; // 区间内数的数量
}
int kth(int rt, int l, int r, int k) {
  if (l == r) return l;
  int m = (l + r) >> 1;
  if (k > tree[lc[rt]]) return kth(rc[rt], m + 1, r, k - tree[lc[rt]]); // 在右半区间内
  return kth(lc[rt], l, m, k); // 在左半区间内
}
int main() {
  cin >> n >> k;
  build(root, 1, n);
  for (int i = 1; i <= n; i++) cin >> a[i];
  sort(a + 1, a + n + 1); // 离散化+去重
  n = unique(a + 1, a + 1 + n) - a - 1; // 记得 -1
  if (k > n) {
    cout << "NO RESULT\n";
    return 0;
  }
  for (int i = 1; i <= n; i++) { update(root, 1, n, i); } // 离散化后,插入下标
  cout << a[kth(root, 1, n, k)] << endl; // 离散化后,kth() 查到的是第 k 小整数的 **下标**
  return 0;
}

注意:离散化时用 unique() 最后面一定要 -1!!!

可持久化权值线段树(主席树)

主席树名称来源于其发明人黄嘉泰的姓名的首字母缩写 HJT。

例题

Luogu-P3834 【模板】可持久化线段树 2

如题,给定 $n$ 个整数构成的序列 $a$,将对于指定的闭区间 $[l, r]$ 查询其区间内的第 $k$ 小值。

$1 \leq n,m \leq 2\times 10^5$,$|a_i| \leq 10^9$,$1 \leq l \leq r \leq n$,$1 \leq k \leq r - l + 1$。


首先看到第 $k$ 小问题,想到要使用权值线段树

对于每一个数,我们都

我们先把问题简化一下:每次求 $[1, r]$ 区间内的 $k$ 小值。

这时,只要找到插入 $r$ 的版本的权值线段树,然后查找即可。

回到原问题:求 $[l, r]$ 区间内的 $k$ 小值。

我们发现,主席树其实具有前缀和的性质,查询 $[l, r]$ 可以转化为 $[1, r]$ 减去 $[1, l-1]$ 的对应区间的大小。

注意数据范围,$2\times 10^5$ 个数,$|a_i| \leq 10^9$,因此用离散化


RECORD

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
int n, m, q;
int a[MAXN], b[MAXN];
int rt[MAXN << 5], lc[MAXN << 5], rc[MAXN << 5], sm[MAXN << 5], tot = 0;
void build(int& rt, int l, int r) {
  rt = ++tot;
  if (l == r) return;
  int m = (l + r) >> 1;
  build(lc[rt], l, m);
  build(rc[rt], m + 1, r);
}
void update(int& rt, int pre, int l, int r, int q) {
  rt = ++tot; // 动态开点
  lc[rt] = lc[pre];
  rc[rt] = rc[pre];
  sm[rt] = sm[pre] + 1;
  if (l == r) return;
  int m = (l + r) >> 1;
  if (q <= m)
    update(lc[rt], lc[pre], l, m, q);
  else
    update(rc[rt], rc[pre], m + 1, r, q);
}
int query(int rt, int pre, int l, int r, int k) {
  if (l == r) return l;
  int x = sm[lc[rt]] - sm[lc[pre]]; // 对应区间相减
  int m = (l + r) >> 1;
  if (x >= k) return query(lc[rt], lc[pre], l, m, k);
  return query(rc[rt], rc[pre], m + 1, r, k - x);
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    b[i] = a[i];
  }
  // 离散化
  sort(b + 1, b + 1 + n);
  q = unique(b + 1, b + 1 + n) - b - 1; 
  build(rt[0], 1, q);
  for (int i = 1; i <= n; i++) {
    int pos = lower_bound(b + 1, b + 1 + q, a[i]) - b;
    update(rt[i], rt[i - 1], 1, q, pos);
  }
  while (m--) {
    int l, r, k;
    scanf("%d%d%d", &l, &r, &k);
    printf("%d\n", b[query(rt[r], rt[l - 1], 1, q, k)]);
  }
  return 0;
}

参考资料