数据结构 2025.6.26

归约

当A问题是B问题的子问题，就是B题的代码能原封不动地用来通过A问题时，我们将B问题认为是难于A问题的。这时候，当我们解决了B问题时，A问题也被解决了，这就叫做将A问题归约到B。

同时，有一些问题能够经过转化变成另一些问题，我们就叫做A问题等价于B问题

复杂度下界

当我们对一个问题完成归约后，如将B问题归约或转化为A问题，则解决A问题的时间复杂度不能低于B问题。

如矩阵乘法（这里认为矩阵乘法的复杂度是

O(n^3)

的，

01

矩阵乘法与

min/max +/ \times

矩阵乘法，即定义矩阵乘法为

c_{i,j} = min_k( a_{i,k} + b_{k,j} )

均是这个复杂度）。树上数颜色难于

\sqrt n /2 \times \sqrt n /2

的矩阵乘法，具体转化如下：

首先，建立一个树高为 $\sqrt n/2$ 的树，这个树有 $\sqrt n/2$ 条链，将链分为前一半和后一半，前一半对应前一个矩阵，后一半对应后一个矩阵，我们这样规定链上的颜色：

当对应的 $\sqrt n \times \sqrt n$ 的矩阵上这个点的值为 $0$ 时，树链上这个点的颜色是任意赋得一个与其他点均不同的一个颜色。

当对应的矩阵上的点为 $1$ 时，此时规定在第 $i$ 条链的 $j$ 个点上，在前一部分颜色是矩阵的 $j$ ，后一部分是矩阵的 $i$ 。

此时， $c_{i,j} = \sum_{k} [a_{i,k}=1][b_{k,j}=1]$ ，等价于链上有多少个相同的颜色

2.每次查询一条两边都是

\sqrt n /2

长的树链，这样树链上的颜色就是

2 * \sqrt n /2 -

前后链上颜色相同的数量。当询问有

O(n)

量级的时候，问题就变成一个完整的矩阵乘法，复杂度不能低于

{\sqrt n /2 }^3

，上界为

O( n^{1.5} )

，即

O(n \sqrt n)

其余问题可以类似证明，问题见ppt即博客

复杂度平衡

这里了解即可，具体内容有

log

分块，如四毛子，将块分组，分别预处理，降低复杂度，具体见题。

k

叉树也可以降低复杂度，这时复杂度单点加是

O(\log_kn)=O(\frac{\log n}{\log k})

，区间加是

O(\frac{\log n}{\log k}k)

。若加的次数是和的

k

倍，那么取

k

叉数最优。

例如，

O(n)

次求和，

O(n \sqrt n)

次加法

k

取

\sqrt n

也就是分块最优。

例题见题解

根号分治

首先，我们要确定哪两个数的乘积小于等于

n

，然后设计阈值和算法来平衡复杂度。

注意，根号分支时，不一定时一直跑一个方法，有可能是像数序列一样，前半段跑一种dp，后半段跑另一种dp，最后用另一种dp统计答案。

势能分析

应用场景：当一些问题，无法直接打tag处理，我们在询问区间完全包含树上区间时，仍要继续向下递归，这时分析复杂度就要使用势能分析

首先，我们要设一个东西来表示势能，当我们每次向下递归时，要保证势能减小，并且每次其他操作完势能不能增加太多，这时复杂度就是正确的。

势能分析例题不会了

信息的性质

可加性，可减性，有逆元，离线与在线（莫二离）强制在线-》二分

文章操作

归约