cdq 分治、整体二分、二进制分组以及高维数点问题总结

本文主要是介绍cdq 分治、整体二分、二进制分组以及高维数点问题总结，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

小螺号呀滴滴地吹，ycx 呀 xjb 写。

数据结构非经典算法

cdq 分治

传统分治算法是当前区间分成两个区间递归下去各解决各自的。cdq 分治是不仅把两部分的子问题都解决了，还让左部分对右部分进行贡献（右对左也行？）。如果左对右贡献的时间复杂度仅与当前处理区间长度 \(n\) 有关，并且是其 polylog，设为 \(f(n)\)，则总复杂度为 \(\mathrm O(f(n)\log n)\)​（这玩意是上界是显然的，同阶的话就感性理解一下吧，大概要用 master 定理？）。

较常见的应用：

1. 数线性结构上（树上可以用 cdq 的拓展——点分治，但我还没学/ll）符合某种条件的数对，左对右贡献就是一个在左部分一个在右部分的数量，由于有 \(mid\) 这个大坝在中间隔着，一般比原问题简单得多，代价是一个 log。
2. 将离线动态数据结构问题转化为离线静态问题，代价是一个 log。前提是修改对询问的贡献有交换律、结合律，而且互相独立。方法是每次左部分的所有修改对右部分的所有询问做贡献，是静态的。
3. 优化 dp。dp 和二分这两玩意看上去是在线，但又不完全是，所以取名曰「半在线」。所以解决 dp 的这 cdq 事实上是改进版本的 cdq，必须是 solve 了左部分，然后左对右贡献，然后 solve 右部分这样一个顺序。因为必须等左部分 dp 值算好之后才能贡献。

二进制分组

只做过一道题，不常用就是了

cdq 想把动态问题转静态问题，需要允许离线。如果强制在线，我们依然有办法将在线动态问题转化为在线静态问题，以一个 log 的代价，前提也是修改对询问的贡献有交换律、结合律、互相独立。

方法是对任意时刻设目前进行了 \(x\) 次修改，将 \(x\) 二进制拆分，实时对每个位权为 \(i\) 的二进制位维护连续 \(i\) 个修改的预处理成果，位权越小维护的修改越新。新加一个修改的时候，令 \(x\) 加一，取低位极长连续 \(1\) 段，加一就是让这些 \(1\) 全变成 \(0\)，然后上一位变成 \(1\)，实现就是把这些 \(1\) 位合并起来加上新加修改放到新的 \(1\)​ 位，可以直接暴力重构。这样子等效于在线静态。查询就直接到 \(\log\) 个修改块里面依次查询，把贡献弄起来。

设预处理 \(n\)​ 个修改复杂度为 \(n\) 的 polylog \(f(n)\)，复杂度证明：

\[\begin{aligned}\mathrm T(n)&=\sum\limits_{i=1}^nf(\mathrm{lowbit}(i))\\&=\sum\limits_{i=1}^{\lfloor\log_2n\rfloor}f\!\left(2^i\right)\left\lfloor\dfrac{n}{2^i}\right\rfloor\\&=\mathrm O(f(n)\log n)\end{aligned} \]

整体二分

我们知道二分这玩意是「半在线」，如果你就把它当在线做，一次回答一个 chk 的话，那免不了受在线问题的局限，比如要预处理一大堆信息，维护的数据结构套层也比较厚。我们有整体二分算法能加大二分的 chk 们的离线程度，前提是题目允许离线。

考虑把所有待二分询问离线下来存到一个序列里，然后一起二分，一开始将它们的二分范围设成一样然后一起 chk。chk 出来一些分到左边一些分到右边，继续递归下去一起 chk。注意到这里某个二分的 log 步之间还是在线关系，但是若干个二分是平行的，整体二分就利用了这一点充分发挥离线的优势一起 chk。

设处理 \(n\) 个询问的 chk 的复杂度是仅关于 \(n\) 的 polylog \(f(n)\)，则总复杂度为 \(\mathrm O(f(n)\log v)\)，其中 \(v\) 是二分范围，不劣于传统二分。整体二分过程中可能不止维护询问序列，还维护了一些对 chk 有贡献的修改序列，这时候需要保证它们每次分裂的时候最多被分到一边（询问的话是自然），此时 \(n\) 是所有序列的总长度。另外若 \(v\)​​ 过大，当询问序列为空时要及时停下来，不然复杂度爆炸。

遇到操作 \(x\) 对 \(mid\geq x\) 都有贡献，这时候有可能不能只分到一边这种情况，通常有两种办法：将待 chk 询问及时减掉 \([l,mid]\)​ 的贡献，这样就可以放心的把前面的贡献只分到前面啦；若无法实现「减掉」，可以令 \([l,mid]\) 子问题做完后，\(\leq mid\) 的操作已经被贡献完毕了，实现是该撤销还是撤销，但是到不继续往下递归的时候要把当前操作序列全部贡献上。

高维数点问题

指的是在 \(d\) 维空间中，有若干个点，每个点有个贡献（交换律、结合律、独立），求第 \(i\) 维不超过 \(x_i\) 所有点贡献和。值域 \(v\)，动态指的是动态加点。

如果是第 \(i\) 维 \(\in[l_i,r_i]\) 这种限制可以差分转化，当然是在贡献可减的情况下。

离线情况的 cdq

离线静态 \(d\)​ 维数点，可以通过给修改、询问的混合序列按第一维排序（注意排序一定要是稳定的，不然修改可能跑到询问后面去！），就变成了一个 \(d-1\) 维动态数点。而 \(d\) 维动态数点可以以一个 log 的代价变成 \(d\) 维静态数点。按照这个思路递归下去。

边界是静态一维数点，不考虑排序 / 二分复杂度是线性。那么静态 \(d\) 维数点是个 \(d-1\) 个 log，动态就是 \(d\) 个。考虑上排序的话，可以发现维数稍高都被平行化掉了，唯有静态一维增加到了 1log。

其实动态一维写 cdq 就是所谓的「归并排序写逆序对」，为了平行化掉排序还非得归并，直接 stable_sort 是 2log（当然更高维就直接 stable_sort 啦），比较麻烦，还是直接 BIT 好写。

在线情况的线段树套层

在线二维静态可以主席树 1log，更高维的 \(d\) 维静态的套层线段树我也不知道能不能可持久化啊啊啊，反正按动态做 \(d\) 个 log 是没问题。

在线动态的话，\(d\) 维就套 \(d\) 个线段树，最外层可以换成 BIT（除非贡献性质不太好，不可减），里面都是动态开点线段树，不然空间不够。空间 \(d-1\) 个 log，时间 \(d\) 个 log。在线三维动态可以二进制分组套主席树复杂度不变，再高维的话二进制分组转化为静态关键是在线高维静态咱不会做啊 5555

应该没有出题人毒瘤到出在线的高维数点吧（高维指的是 3 维以上）。。。。

bitset 奇技淫巧

如果真的是「数」点，也就是每个点权为 \(1\)​，合并贡献是加法，那有个奇技淫巧。考虑第 \(i\) 维不超过 \(x_i\) 的点的集合，用 bitset 存，然后把 \(d\) 维交起来即可。

实现不需要什么「可持久化 bitset」，直接对每维扫一遍前缀和预处理即可，前提是能存的下。时空复杂度都是 \(\mathrm O\!\left(\dfrac{dn^2}w\right)\)。注意到 \(d\) 这里作为一个因子成在前面，而不是指数，所以维数上升没什么影响。

这篇关于cdq 分治、整体二分、二进制分组以及高维数点问题总结的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！