Note: This article is available in Chinese only. 本文暂无英文版本。
View original
起因是队里的大佬们都会这东西，而我一个老年选手竟然还不会，实在说不过去。
cdq分治显然是分治的一种，cdq的意思就是超短裙啦（
这东西网上资料很多（然而还是学不会
先放一波资料：
下面转自lwt菊苣的博客，豁然开朗。
1 * 与普通分治的区别普通分治中，每一个子问题只解决它本身（可以说是封闭的） CDQ分治中，对于划分出来的两个子问题，前一个子问题用来解决后一个子问题而不是它本身
1 * 适用的情况在很多问题中（比如大多数数据结构题），经常需要处理一些动态问题 然而对动态问题的处理总是不如静态问题来的方便，于是就有了CDQ分治 但使用CDQ分治的前提是问题必须具有以下两个性质：
1 * 修改操作对询问的贡献独立，修改操作互不影响效果
2 * 题目允许使用离线算法。
3
4
5 * 一般步骤
6
7 * 将整个操作序列分为两个长度相等的部分（分）
8 * 递归处理前一部分的子问题（治1）
9 * 计算前一部分的子问题中的修改操作对后一部分子问题的影响（治2）
10 * 递归处理后一部分子问题（治3）特别说明： 在整个过程中，最核心的就是步骤3 此时前一部分子问题中的修改操作相对后一部分子问题来说是静态处理，因此可以更加方便地计算后一部分子问题
cdq分治求三维偏序美滋滋
一般是，第一维排序，第二维cdq,第三维套一层数据结构（不然的话就要数据结构套数据结构啦差评
cdq的复杂度和分治的复杂度一样也是O(nlgn),所以可以理解成cdq可以一层数据结构？因为比树套树之类好写，所以有广泛应用（？