CDQ分治

CDQ分治
CDQ分治，又称基于时间的分治算法，常用于解决多维偏序问题。该算法可以通过增加log(n)的代价将偏序问题降掉一维，从而转化成更易解决的多维偏序问题。事实上，CDQ分治能解决的题目很多都可以用支持动态查询的高级数据结构完成，但是CDQ分治的思维难度和代码实现难度较于高级数据结构减小了很多，并且空间更小。 有些题目要求诸如：只有修改操作的属性值小于（或大于）某一询问操作的答案，该修改操作才能对询问产生影响。这里，我们视操作顺序为第一维，属性值为第二维，修改/询问的值为第三维，发现这就是三维偏序问题。

一、大致思路
我们拿逆序对这个二维偏序问题开始说。对于逆序对，我们可以分治排序，也可以先排序再用一个树状数组求出来。那么如果我们能用一种手段把三维偏序问题降维，就可以很容易地解决了。那么怎么降维？答案是，用分治！ 于是我们的重点就转化称如何用分治降维。 值得一提的是，CDQ分治大致有两个基本形式：

CDQ分治最先出现在Python成神之路。