早教篇：高维累加与高维求和

H_Kaguya · 2022-11-23 19:54:47 · 个人记录

↑把胎教当早教

有人说我不经常发博客，所以。。。
本文纯属发风。(保证说的不是对的) 不保证说的是对的，如有问题直接扬了就行。

以下记录一下利用 CDQ 解决高维累加与高维求和问题的普适性方法。。。
巨佬早就会了的话请跳过。

以下探讨的所有问题均在不强制在线的前提下。

最初的问题

接下来整几道水题。

1. 给一个序列，区间加，区间求和，所有操作在查询之前。

显然，先差分去完成修改，再做两次前缀，然后去解决查询。
时间复杂度：O(N)。

2. 给一个序列，区间加，区间求和，修改和询问在一起。

树状数组/线段树板子题。不过多解释。
时间复杂度：O(N log_2 N)。

3. 给一个平面，矩形加，矩形求和，所有操作在查询之前。

按照树状数组维护区间加区间和的思路，将平面拆分成两个：差分和一次前缀。
这样，就将所有的操作和询问都变成了一条线。
然后再去用树状数组/线段树维护扫描线。
时间复杂度：O(N log_2 N)。

4. 给一个平面，矩形加，矩形求和，修改和询问在一起。

二维树状数组/树套树，直接维护。
时间复杂度：O(N log_2^{\ 2} N)。

5. 给一个立方体，立方体加，立方体求和
6. 给一个四维体，
7. .........

按照如上套路，我们可以出 \inf 道题。

我们会发现，以上问题大体上可以分为两种：在线的和离线的。
但是会有一个小规律：在线的 w - 1 维问题和离线的 w 维问题的时间复杂度相同。
这是巧合吗？（虽然但是，很可能是）

问题转化

那么，我们可以试着将在线的问题转化成离线的。
考虑问题 2,我们可以手动增加一个时间维度，将问题升上二维。
那么，每一次修改就相当于是一个矩形加（作用于时间维度上），每一次的查询仍然是查询一条线的和。
然后我们发现，这个问题和问题 3 是等价的，直接按照问题 3 的方法去做就行了。
然后发现其实常数大了不少。

而同理，其实可以将问题 3 转化为问题 2，但是必须在线处理。
于是，我们可以将上述问题中所有在线的问题升上一维，变成离线的。
接下来只需要考虑离线问题如何求解即可。

使用工具

考虑我们手中有什么可以解决这类问题的东西：

1. 树状数组/线段树 消耗一个 log 的复杂度在解决在线一维问题。
2. 扫描线。不消耗时间复杂度，将一个离线问题削掉一维，同时转化为在线的。
3. 差分。消耗一个 2 的常数，将操作和查询全部削掉一维（原问题维数不变）

显然，扫描线是消耗品，当问题被转化成了在线的时候这个东西就没用了。
因此，利用上述工具，最多只能解决到二维问题。

于是，我们需要解决三维偏序的模板算法：CDQ 分治。

此时我们发现，好像扫描线没用了，那就扔了吧。
不过，扫描线可以帮我们合理利用时间维度。这部分下次再说。

再扔一个

既然说是要用 CDQ 解决问题，那么树状数组/线段树是来干什么的呢。
于是就考虑应该把这东西也扔了。
请出一个功能更加强大的数据结构：

5. 数组。 消耗 O(1) 的时间复杂度完成单点修改/单点查询。

怎么样，厉害吧。
既然 CDQ 可以消掉一维，那么直接用 CDQ 将二维偏序削成一维偏序不就好了。
这样，就可以用数组来解决问题了。
（先不考虑常数和效率问题）

同时，为了保证 CDQ 的时间复杂度正确，需要在 CDQ 的同时使用归并排序进行离散化。
毕竟最内层的一维偏序是 O(N) 的，怎么能搭配 O(N log_2 N) 的排序呢。
这样，我们就成功的找到了解决这类问题的普适性方法。

具体说明

貌似刚才说的有点抽象，我们再具体分析一下。

首先，拿到一个问题，在 w 维平面上进行平面加，平面求和。
第一步，将时间维度拍上去，问题升上 w + 1 维。
第二步，进行差分，将修改和查询降回 w 维。
第三步，按照被差分掉的那一维排序，进行 CDQ 分治。
合并区间时需要考虑左边对右边的贡献，可以直接将左边的修改和右边的查询拿出来，然后问题转化成了一个 w 维的累加与求和问题，并且问题是离线的，递归求解。

我们发现，w + 1 维的问题需要进行 w 次 CDQ 才可以降到 1 维，所以时间复杂度是 O(N log_2^{\ w}N) 的。

严谨分析

看上去时间复杂度还不错，但事实上真的是这样吗？
考虑前面提到的差分。

消耗一个 2 的常数

但是，我们会发现，每一维都会重复如上操作，所以这个东西是一个二叉树的样子。
一些不好的直觉告诉我们，这个东西的复杂度可能是指数级别的。

让我们拿出主定理算一算吧。
写出式子：

然后我发现我不会主定理。
去求助巨佬。这东西的复杂度貌似是 O(2^w N log_2^{\ w - 1}N) 的。
所以，这是一个指数级算法。。。
不过平时常见的都是四维及以下的，所以前面那个可以看成常数。

end

回到最初的问题。
我仍然认为及二维以下的问题用树状数组更好一点。

今天又说了一堆废话。
一句话概括：用 CDQ 套 CDQ 打了个 w 维偏序。

那么，这个问题就到这里结束吧（心情简单）

发现一个问题。
每次每个操作和查询也会被差分成两个。
所以其实复杂度可能是 O(4^w N log_2^{\ w - 1}N)。
或许会根据实现的不同有所差别吧。

丢一个四维偏序水题进来。
P4849 寻找宝藏

还是那个复杂度的问题。
我们发现，在分析渐进复杂度的时候，4^w \log_2^{w - 1} N 其实可以被认为就是 \log_2^{w - 1}。
毕竟和 \log n 比起来 4 只是一个常数。
所以复杂度应该写成 O(n \log^{w - 1} n)。