CDQ分治 笔记

CDQ 分治可以方便的代替一些数据结构,但是是离线的。

比如最常见的归并排序求逆序对,其实就是 CDQ 分治。

CDQ 分治的大体思想是将带求解区间一分为二,然后分别求解左边区间里的答案,右边区间里的答案,以及左边对右边的影响。数学归纳法可以证明这样子是对的。

比如最简单的逆序对也就是二维偏序,每次将左边有序区间与右边有序区间合并时就能统计左边对右边的影响也就是产生的逆序对,排序的过程实际上只是为了方便这个统计"左边区间对右边区间的影响"。

CDQ 分治套数据结构

考虑一下二维偏序的升级版,三维偏序该怎么用 CDQ 分治来做?

可以在二维偏序的基础上套一个线段树 / 树状数组,来保证第三维的有序。

如果,再升级一下,四维偏序该怎么解决?

CDQ 分治套 CDQ 分治

四维偏序的问题就在于:我们该怎么统计左边区间对右边区间的影响?

当左边区间与右边区间的答案都已计算完毕,左边区间与右边区间的第一维已经是有一个相对顺序了。那么考虑再做一个 CDQ 分治来计算左边区间对右边区间的影响。因为只需要考虑左区间对右区间的影响,将每个位置都标记一下是左区间的还是右区间的,开始第二维 CDQ 分治。还是先处理左右两边的原属于左区间的数字对原属于右区间的影响,再考虑左区间对右区间的影响。现在只要再套一个树状数组就行了。当然更高维的偏序也可以套多个 CDQ 分治。

CDQ 分治优化 DP

考虑一下最长上升子序列怎么不用数据结构优化做到 $\mathcal O(n\cdot\log_2n)$?

还是可以用 CDQ 分治。

先考虑左边的答案,再考虑左边对右边的影响,最后再计算右边的答案。

一些应用

  • 偏序。
  • 一些矩阵类统计问题将查询写成前缀和相加相减的形式,然后如果待修改的话就加一个时间戳,只有时间戳有序才能造成影响,统计的方式跟偏序问题差不多。

CDQ 分治的中心思想就是考虑左边区间对右边区间的影响,遇到问题时 CDQ 分治可以作为一个解题的方向。

最后修改:2019 年 08 月 16 日 10 : 46 AM

发表评论