线段树 解题技巧

发表于 分类于 阅读次数： Waline： 本文字数： 945 阅读时长 ≈ 3 分钟

编程技巧

普通线段树

难点主要集中在标签下放与合并

在编程更新函数时，要考虑对同一区间反复更新不同标签的合并优先级；

该优先级也同样会应用到标签下放操作上。

分治

可以左右对半分，可以偏左子树，可以偏右子树，完全服务于题目。

二分

二分依赖单调性，答案要么在左孩子，要么在右孩子，故而考虑左右孩子的优先级。

假设当前数组为升序，用其初始化线段树，求大于v的最小值下标。

那么应该保存每个区间的最大值，如果左孩子的最大值大于v，说明可能存在解，优先处理左孩子；

因为数组是升序，假设左右孩子都有解，显然左孩子的解才是正确答案。

动态开点

一般用在区间范围过大，无法使用普通线段树的情况下。

普通线段树的空间开销是4 * 数据范围，动态开点线段树的空间开销是询问次数 * log数据范围，小了很多。

动态开点的编程也与普通线段树有细微差距，区间范围通过函数的参数传递，如果左右孩子不存在需要即时创建。

合并

有合并、主席树两种思维。

合并思维并不会新开额外空间，是因为把所有子树的数据并到父树上；

但存在致命缺陷，父树合并子树结构后，子树很有可能会在父树合并期间被篡改原有数据，

所以不可以在合并后进行子区间的访问。

主席树思维则没有这个弊端，毕竟每次合并都会新开一个节点；当然代价就是空间占用过大，毕竟相当于直接新建一颗新树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 合并思维
int merge(int p, int q, int l, int r) {
  if (!p) return q;
  if (!q) return p;
  if (l == r) {
    s[p] += s[q];
    return p;
  }
  int mid = (l + r) >> 1;
  lc[p] = merge(lc[p], lc[q], l, mid);
  rc[p] = merge(rc[p], rc[q], mid + 1, r);
  s[p] = s[lc[p]] + s[rc[p]];
  return p;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 主席树新建节点思维
int merge(int p, int q, int l, int r) {
  if (!p || !q) return p + q;
  if (l == r) {
    sum[++cnt] = sum[p] + sum[q];
    return cnt;
  }
  int mid = l + r >> 1;
  int u = ++cnt;
  lc[u] = merge(lc[p], lc[q], l, mid);
  rc[u] = merge(rc[p], rc[q], mid + 1, r);
  sum[u] = sum[lc[u]] + sum[rc[u]];
  return u;
}

练习题

  • P3372 区间和
  • P3870 区间取反
  • P1438 差分、区间和
  • P1253 多标签处理（多标签可以抵消），区间覆盖、区间新增、区间极值
  • P3373 多标签处理（多标签可以抵消），区间乘法，区间加法
  • P4513 分治（左右孩子互不影响）
  • P1471 区间方差和
  • P4692 分治（左右孩子互不影响）
  • P1637 权值线段树/权值树状数组
  • P1558 区间与运算，状态压缩
  • P5522 区间交运算，状态压缩
  • 689D 区间极值
  • P4145 势能线段树
  • P2572 分治（左右孩子互不影响），多标签处理，区间覆盖，区间取反；模板题
  • P4198 分治（左孩子影响右孩子），模板题
  • P5579 线段树二分，最大值里找最小
  • 2828 线段树二分，答案要么在左孩子要么在右
  • 4747 线段树二分，最大找最小
  • 19D 线段树二分，set优化，满足条件下找最小，模板题
  • P5459 动态开点线段树
  • 915E 动态开点线段树，模板题
  • 353 线段树合并，LCA，树上差分，合并写法，模板题
  • P3899 线段树合并，主席树写法，模板题
  • P3224 线段树合并，并查集
  • P3605 线段树合并
  • P3521 线段树合并，逆序对