知识清单

• 序列分治
• 树上点分治
• 树链剖分

上午依然不能上网好气啊$qwq$

笔记

1. 序列分治？？？

   • 例：一个长为$N$的序列（$a_1,a_2,a_3,.....a_N$），求

     $$\sum\limits_{l=1}^N \sum\limits_{r=l}^N max(a_l,a_{l+1},...,a_r)$$

     求出这个数列的前缀$Max$和后缀$Max$。

2. 树上点分治？？？？

3. 树链剖分

   • 上次咕咕咕了，现在补全$QAQ$
   • 作用：主要是路径权值和、路径最大值等一些线段树可以做出来的序列维护，但是树链剖分可以移植到一棵树上。
   • 概念：
     • 重儿子：子节点中子树节点数最多的结点
     • 轻儿子：不是重儿子的儿子结点
     • 重边：父节点与重儿子的边
     • 轻边：父节点与轻儿子的边
     • 重链：相连的多条重边所组成的路径
     • 轻链：相连的多条轻边所组成的路径