线段树解题技巧

发表于 2024-09-22 分类于解题技巧 Waline：本文字数： 945 阅读时长 ≈ 3 分钟

编程技巧

普通线段树

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

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

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

分治

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

二分

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

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

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

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

动态开点

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

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

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

合并

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

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

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

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

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

// 合并思维
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;
}

// 主席树新建节点思维
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;
}