靜海遺跡
~ Esoteria Algorithm in Reverse Observatory
归档
·
标签
·
关於
·
友链
·
开往
轻重链剖分与树上路径操作
Prologue
前置技能
大法师
线段树
LCA
一些定义
树上的路径称为树链
非叶节点的儿子中子树大小最大的儿子为重儿子,其它为轻儿子
从非叶节点到重儿子的边称为重边,其它为轻边
由重边构成的链称为重链,其它为轻链
重链中深度最小的节点为链顶
重链的链顶都是其父节点轻儿子
轻叶节点独自构成一条重链
将树分割为重链和轻链即为剖分
树链剖分就是用数据结构去维护重链和轻链
左闭右开区间跟国际接轨
Posted at 10/24/2018
·
笔记
·
算法