~ Esoteria Algorithm in Reverse Observatory

轻重链剖分与树上路径操作

Prologue

前置技能

一些定义

  • 树上的路径称为树链
  • 非叶节点的儿子中子树大小最大的儿子为重儿子,其它为轻儿子
  • 从非叶节点到重儿子的边称为重边,其它为轻边
  • 由重边构成的链称为重链,其它为轻链
    • 重链中深度最小的节点为链顶
    • 重链的链顶都是其父节点轻儿子
    • 轻叶节点独自构成一条重链
  • 将树分割为重链和轻链即为剖分
  • 树链剖分就是用数据结构去维护重链和轻链
  • 左闭右开区间跟国际接轨

分块

Prologue

  • 块:将一个数列分为若干个不相交区间,每一个区间称为块
  • 完整块:进行区间操作时被区间完全覆盖的块
  • 不完整块:进行区间操作时部分被区间覆盖的块

倍增 LCA

Prologue

给定一棵有根树,若节点 zz 既是节点 xx 的祖先,也是节点 yy 的祖先,则称 zzx,yx,y 的公共祖先。在 x,yx,y 的所有公共祖先中,深度最大的一个称为 x,yx,y 的最近公共祖先,记为 LCA(x,y)\text{LCA} (x,y)

线段树

Introduction Chapter

有一类问题,数据通常可以建模到数轴或是数列上,操作一般是每次对数轴上的一个区间或是数列中的连续若干个数进行修改、查询等,数据规模往往比较大。这些数据就适合用线段树维护。