线段树分治-陈丹琪(cdq)分治

很显然，我们在进行操作的时候，把所有操作都放在一棵树里面，就像遍历一棵树一样遍历一整棵树，这个算法与回溯+$dfs$不同的地方在于一层递归中有可能横跨多个节点。如果一个操作需要用到多个节点，那么就把这个操作拆开，分治这个操作，最多能分成$log$级别数量的操作。

模仿线段树，将这个操作覆盖整个区间，然后进行拆分操作，递归子树求解。

它只支持离线操作，但是它的常数比较小，能替代一部分比较复杂的数据结构。

~~（CDQ分治太烦了，学习中……）~~

更多详情请点击Coco_T_大佬的blog。