2019.5.12高中部集训

知识清单

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

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


笔记

  1. 序列分治???

    • 例:一个长为$N$的序列($a_1,a_2,a_3,…..a_N$),求

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

  2. 树上点分治????

  3. 树链剖分

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

Update your browser to view this website correctly. Update my browser now

×