分治

一、简单介绍

二、集中题目

1、  动态最小生成树（了解）

2、  CDQ分治

（1）       蝗虫（运用）

（2）       CASH（了解）

（3）       共点圆（了解）

3、  树分治

（1）       树链剖分（运用）  例题：：BZOJ2243

每个点记录siz、son、fa、top、dfn

（siz：该点子树大小、son：该点重链上的儿子（就是重儿子），top：该点重链的顶端，如果不在重链上则top=本身）

先dfs一遍，求出siz，son，fa

再dfs一遍（依照优先dfs重儿子）求出top和dfn

求lca也可以用树链剖分，每个点记一个dep即可。

                     （2）点分治（了解）

分治笔记