day14 线段树

常规
1

线段树常见应用

基础

应用

  • 在 O(\log N) 的复杂度内单点/区间修改、区间查询（区间求和，求区间最大/小值）

原理

  • 将每个长度不为 1 的区间划分成左有两个区间递归求解，把整个线段划分为一个树形结构
  • 通过合并左右两区间信息来求得该区间的信息

实现

  • 考虑递归建树
  • 设当前根节点为 p ，如果根节点管辖的区间长度已经是 1 ，则可以直接根据 a 数组上相应位置的值初始化该节点
  • 否则将该区间从中点处分割为两个子区间，分别进入左右子节点递归建树，最后合并两个子节点的信息
  • 一般开 4\times n 的空间
  • 区间修改的时候使用懒惰标记，等到访问到该节点后才更新节点信息

进阶

动态开点

  • 为了节省空间，可以不一次性建好树，最初只建立一个根节点代表整个区间
  • 当需要访问某个子区间时，才建立代表这个区间的子节点
  • 节点只有在需要的时候才被创建

标记永久化

  • 如果确定懒惰标记不会在中途被加到溢出，那就可以将标记永久化
  • 只需在进行讯问时把标记的影响加到答案当中，降低常熟
  • 用于树套树和可持久化数据结构中会用到的一种技巧

静态线段树

  • 当需要询问区间线性基这种合并复杂度高达 O(\log^2w) 的信息时， O(\log n) 次合并在时间上有时是不可接受的
  • 构造静态线段树需要 O(n\log n) 次合并操作，但是此时的查询复杂度被加速至 O(1) 次合并操作
  • 设线段树上一个节点代表的区间为 (l,r]
  • 在这个节点中额外保存 (l,mid] 的后缀和数组和 (mid,r] 的前缀和数组
  • 建树时间复杂度为 T(n)=2T(n/2)+O(n) = O(n\log n) ，空间复杂度为 O(n\log n)
  • 假设询问的区间是 [l,r] ，那么把代表 [l,l] 的节点和代表 [r,r] 的节点的 LCA 求出来，记为 p
  • l,r 在 p 所包含的区间之内，并且一定跨越了 p 的中点
  • 说明可以使用 p 里的前缀和数组和后缀和数组，将 [l,r] 拆成 [l,mid]+(mid,r] 从而拼出 [l,r] 这个区间
  • 这个合并操作是 O(1) 的，而线段树上两个节点的 LCA 编号，就是两个节点二进制编号的最长公共前缀 LCP
  • lcp(x,y)=x >> log[x^y]
5 个赞
2

tjl

2 个赞