标签：树链 | 靜海遺跡

Prologue

前置技能

• 大法师
• 线段树
• LCA

一些定义

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