Abel 变换，离散型分部积分
文章目录
- 零、引入：分部积分
- 一、Abel 变换
- 1.1 Abel 变换
- 1.2 证明
- 二、一些比较浅显的应用
- 2.1 等差 乘 等比型求和
- 2.2 平方求和公式
- 2.3 不等式证明
- 三、一些算法题的式子优化
- 3.1 3500.将数组分割为子数组的最小代价
- 3.2 D. Array Splitting
- 3.3 300. 任务安排1
零、引入：分部积分
我们不难表示出上图中 的面积 A1 和 A2
A 1 = ∫ y 1 y 2 x d y A 2 = ∫ x 1 x 2 y d x A 1 + A 2 = x 2 y 2 − x 1 y 1 ∫ x d y + ∫ y d x = x y ∫ x d y = x y − ∫ y d x \begin{align} & A1 = \int_{y_1}^{y_2} xdy \\ & A2 = \int_{x_1}^{x_2} ydx \\ & A_1 + A_2 = x_2y_2 - x_1y_1\\ & \int xdy + \int ydx = xy \\ & \int xdy = xy - \int ydx \end{align} A1=∫y1y2xdyA2=∫x1x2ydxA1+A2=x2y2−x1y1∫xdy+∫ydx=xy∫xdy=xy−∫ydx
这也是我们常用的 分部积分公式
一、Abel 变换
1.1 Abel 变换
Abel变换，又称为Abel分部求和（summation by parts），相当于分部积分的离散版本。
它有如下表示：
∑ i = m n a i b i = A n b n − ∑ i = m n − 1 A i ( b i + 1 − b i ) 其中， A i = ∑ k = m i a k \begin{align} & \sum_{i=m}^{n} a_ib_i = A_nb_n - \sum_{i=m}^{n-1}A_i(b_{i+1} - b_i) \\ & 其中，A_i = \sum_{k=m}^{i}a_k \end{align} i=m∑naibi=Anbn−i=m∑n−1Ai(bi+1−bi)其中，Ai=k=m∑iak
1.2 证明
可以直接式子变形来推导：
∑ i = m n a i b i = ∑ i = m n ( A i − A i − 1 ) b i = A n b n − A n − 1 b n + A n − 1 b n − 1 − A n − 2 b n − 2 + . . . + A m + 1 b m + 1 − A m b m + 1 + A m b m = A n b n − ∑ i = m n − 1 A i ( b i + 1 − b i ) \begin{align} & \ \ \ \ \ \sum_{i=m}^{n} a_ib_i \\ &= \sum_{i=m}^{n} (A_i - A_{i-1})b_i \\ &= A_n b_n - A_{n-1}b_n + A_{n-1}b_{n-1} - A_{n-2}b_{n-2} + ... + A_{m+1}b_{m+1} - A_{m}b_{m+1} +A_{m}b_m \\ &= A_nb_n - \sum_{i=m}^{n-1} A_i(b_{i+1} - b_i) \end{align} i=m∑naibi=i=m∑n(Ai−Ai−1)bi=Anbn−An−1bn+An−1bn−1−An−2bn−2+...+Am+1bm+1−Ambm+1+Ambm=Anbn−i=m∑n−1Ai(bi+1−bi)
也可以从几何上来理解：
我们以 m = 1 为例：
我们要求和的部分为对角线元素，那么对角线之和可以表示为 大梯形 - 小梯形，或者说每行的差分求和
即：
∑ i = 1 n a i b i = ∑ i = 1 n a i b n − ∑ i = 1 n − 1 a i b n + ∑ i = 1 n − 1 a i b n − 1 − ∑ i = 1 n − 2 a i b n − 2 + . . . + ∑ i = 1 2 a i b 2 − a 1 b 2 + a 1 b 1 = A n b n − ∑ i = m n − 1 A i ( b i + 1 − b i ) \begin{align} & \ \ \ \ \sum_{i=1}^{n}a_ib_i \\ &= \sum_{i=1}^{n}a_ib_n - \sum_{i=1}^{n-1}a_ib_n + \sum_{i=1}^{n-1}a_ib_{n-1} - \sum_{i=1}^{n-2}a_ib_{n-2} + ... + \sum_{i=1}^{2}a_ib_2 - a_1b_2 + a_1b_1 \\ &= A_nb_n - \sum_{i=m}^{n-1} A_i(b_{i+1} - b_i) \end{align} i=1∑naibi=i=1∑naibn−i=1∑n−1aibn+i=1∑n−1aibn−1−i=1∑n−2aibn−2+...+i=1∑2aib2−a1b2+a1b1=Anbn−i=m∑n−1Ai(bi+1−bi)
利用 Abel 变换，可以证明很多涉及到乘积的求和的问题，因为它可以将乘积的求和表示为求和的乘积。
二、一些比较浅显的应用
2.1 等差 乘 等比型求和
高中常用方法是错位相减法，有了 Abel 变换，可以更为快速的求解。
设有 ai 为公差为d等差数列，bi 为首项为1公比为 q 的等比数列，我们要求 ∑ i = 1 n a i b i \sum_{i=1}^{n}a_ib_i ∑i=1naibi
记 bi 的前n项部分和为 Bn
∑ i = 1 n a i b i = a n B n − ∑ i = 1 n − 1 d B i = a n q ( 1 − q n ) 1 − q − ∑ i = 1 n − 1 d q ( 1 − q i ) 1 − q \begin{align} & \ \ \ \ \sum_{i=1}^{n}a_ib_i \\ &= a_nB_n - \sum_{i=1}^{n-1} d B_{i} \\ &= a_n \frac{q(1-q^n)}{1-q} - \sum_{i=1}^{n-1} d \frac{q(1-q^i)}{1-q} \end{align} i=1∑naibi=anBn−i=1∑n−1dBi=an1−qq(1−qn)−i=1∑n−1d1−qq(1−qi)
2.2 平方求和公式
我们熟知 ∑ i = 1 n i 2 = n ( n + 1 ) ( 2 n + 1 ) 6 \sum_{i=1}^{n}i^2 = \frac{n(n+1)(2n+1)}{6} ∑i=1ni2=6n(n+1)(2n+1)
可以看成 ai = bi = i，我们记 要求的式子为 S(n)
可以轻松的用 Abel 变换来推导：
S ( n ) = ∑ i = 1 n i 2 = n 2 ( n + 1 ) 2 − ∑ i = 1 n − 1 i 2 + i 2 = n 2 ( n + 1 ) 2 − n ( n − 1 ) 4 − S ( n ) − n 2 2 解得 : S ( n ) = n ( n + 1 ) ( 2 n + 1 ) 6 \begin{align} S(n) &= \sum_{i=1}^{n}i^2 \\ &= \frac{n^2(n+1)}{2} - \sum_{i=1}^{n-1}\frac{i^2+i}{2} \\ &= \frac{n^2(n+1)}{2} - \frac{n(n-1)}{4} - \frac{S(n)-n^2}{2} \\ & 解得: S(n) = \frac{n(n+1)(2n+1)}{6} \end{align} S(n)=i=1∑ni2=2n2(n+1)−i=1∑n−12i2+i=2n2(n+1)−4n(n−1)−2S(n)−n2解得:S(n)=6n(n+1)(2n+1)
2.3 不等式证明
来自知乎学数相伴
证明不等式 : 2 3 n n < ∑ i = 1 n i < 4 n + 3 6 n 证：我们分两步来证明，先证左侧不等式，再证右侧不等式。 首先左侧，考虑 a n = 1 , b n = n ，设 S = ∑ i = 1 n i ，我们应用 A b e l 变换，则有： S = b n A n − ∑ i = 1 n − 1 ( b i + 1 − b i ) A i = n n − ∑ i = 1 n − 1 ( i + 1 − i ) i 因为： ( n − 1 ) ( n − n − 1 ) = ( n − 1 ) 1 n + n − 1 < n − 1 2 n − 1 = n − 1 2 因此： S > n n − 1 2 ( 1 + 2 + ⋯ + n − 1 ) = n n − 1 2 ( S − n ) 即 S > 2 n + 1 3 n > 2 n 3 n ，左侧证明完成。 右侧证明，类似，考虑 a n = n , b n = 1 n ，设 S = ∑ i = 1 n i , A n = n ( n + 1 ) 2 ， 同样应用 A b e l 变换： S = b n A n − ∑ i = 1 n − 1 ( b i + 1 − b i ) A i = 1 n n ( n + 1 ) 2 − ∑ i = 1 n − 1 ( 1 i + 1 − 1 i ) i ( i + 1 ) 2 ( 1 m − 1 − 1 m ) m ( m − 1 ) 2 = m − m − 1 m − 1 ⋅ m ⋅ m ( m − 1 ) 2 = m ( m − 1 ) ( m − m − 1 ) 2 = m ( m − 1 ) 2 ( m + m − 1 ) 由基本不等式 a b a + b ≤ a + b 4 得到： ( 1 m − 1 − 1 m ) m ( m − 1 ) 2 ≤ m + m − 1 8 因此： S = 1 n n ( n + 1 ) 2 − ∑ i = 1 n − 1 ( 1 i + 1 − 1 i ) i ( i + 1 ) 2 = 1 n n ( n + 1 ) 2 + ∑ i = 1 n − 1 ( 1 i − 1 i + 1 ) i ( i + 1 ) 2 S < n + 1 2 n + 1 8 ( 1 + 2 + 2 + + 3 + 3 + ⋯ + n − 1 + n − 1 + n ) = n + 1 2 n + 1 8 ( 2 S − 1 − n ) 整理得： S < ( 4 n + 3 ) n − 1 6 < ( 4 n + 3 ) 6 n 右侧不等式得证，而且得到更精细的不等式。 \begin{align} & 证明不等式: \frac{2}{3} n \sqrt{n}<\sum_{i=1}^{n} \sqrt{i}<\frac{4 n+3}{6} \sqrt{n} \\ & 证：我们分两步来证明，先证左侧不等式，再证右侧不等式。\\ & 首先左侧，考虑 a_{n}=1, b_{n}=\sqrt{n} ，设 S=\sum_{i=1}^{n} \sqrt{i} ，我们应用Abel变换，则有：\\ & S=b_{n} A_{n}-\sum_{i=1}^{n-1}\left(b_{i+1}-b_{i}\right) A_{i}=n \sqrt{n}-\sum_{i=1}^{n-1}(\sqrt{i+1}-\sqrt{i}) i \\ & 因为： (n-1)(\sqrt{n}-\sqrt{n-1})=(n-1) \frac{1}{\sqrt{n}+\sqrt{n-1}}<\frac{n-1}{2 \sqrt{n-1}}=\frac{\sqrt{n-1}}{2} \\ & 因此： S>n \sqrt{n}-\frac{1}{2}(\sqrt{1}+\sqrt{2}+\cdots+\sqrt{n-1})=n \sqrt{n}-\frac{1}{2}(S-\sqrt{n}) \\ & 即 S>\frac{2 n+1}{3} \sqrt{n}>\frac{2 n}{3} \sqrt{n} ，左侧证明完成。\\ & 右侧证明，类似，考虑 a_{n}=n, b_{n}=\frac{1}{\sqrt{n}} ，设 S=\sum_{i=1}^{n} \sqrt{i}, A_{n}=\frac{n(n+1)}{2} ，\\ & 同样应用Abel变换： S=b_{n} A_{n}-\sum_{i=1}^{n-1}\left(b_{i+1}-b_{i}\right) A_{i}=\frac{1}{\sqrt{n}} \frac{n(n+1)}{2}-\sum_{i=1}^{n-1}\left(\frac{1}{\sqrt{i+1}}-\frac{1}{\sqrt{i}}\right) \frac{i(i+1)}{2} \\ & \left(\frac{1}{\sqrt{m-1}}-\frac{1}{\sqrt{m}}\right) \frac{m(m-1)}{2}=\frac{\sqrt{m}-\sqrt{m-1}}{\sqrt{m-1} \cdot \sqrt{m}} \cdot \frac{m(m-1)}{2}\\ & \begin{array}{l} =\frac{\sqrt{m(m-1)}(\sqrt{m}-\sqrt{m-1})}{2} \\ =\frac{\sqrt{m(m-1)}}{2(\sqrt{m}+\sqrt{m-1})} \end{array} \\ & 由基本不等式 \frac{a b}{a+b} \leq \frac{a+b}{4} \\ & 得到： \left(\frac{1}{\sqrt{m-1}}-\frac{1}{\sqrt{m}}\right) \frac{m(m-1)}{2} \leq \frac{\sqrt{m}+\sqrt{m-1}}{8} \\ & 因此：\\ S & =\frac{1}{\sqrt{n}} \frac{n(n+1)}{2}-\sum_{i=1}^{n-1}\left(\frac{1}{\sqrt{i+1}}-\frac{1}{\sqrt{i}}\right) \frac{i(i+1)}{2}=\frac{1}{\sqrt{n}} \frac{n(n+1)}{2}+\sum_{i=1}^{n-1}\left(\frac{1}{\sqrt{i}}-\frac{1}{\sqrt{i+1}}\right) \frac{i(i+1)}{2} \\ S & <\frac{n+1}{2} \sqrt{n}+\frac{1}{8}(\sqrt{1}+\sqrt{2}+\sqrt{2}++\sqrt{3}+\sqrt{3}+\cdots+\sqrt{n-1}+\sqrt{n-1}+\sqrt{n}) \\ & =\frac{n+1}{2} \sqrt{n}+\frac{1}{8}(2 S-1-\sqrt{n}) \\ & 整理得： S<\frac{(4 n+3) \sqrt{n}-1}{6}<\frac{(4 n+3)}{6} \sqrt{n} \\ & 右侧不等式得证，而且得到更精细的不等式。 \end{align} SS证明不等式:32nn<i=1∑ni<64n+3n证：我们分两步来证明，先证左侧不等式，再证右侧不等式。首先左侧，考虑an=1,bn=n，设S=i=1∑ni，我们应用Abel变换，则有：S=bnAn−i=1∑n−1(bi+1−bi)Ai=nn−i=1∑n−1(i+1−i)i因为：(n−1)(n−n−1)=(n−1)n+n−11<2n−1n−1=2n−1因此：S>nn−21(1+2+⋯+n−1)=nn−21(S−n)即S>32n+1n>32nn，左侧证明完成。右侧证明，类似，考虑an=n,bn=n1，设S=i=1∑ni,An=2n(n+1)，同样应用Abel变换：S=bnAn−i=1∑n−1(bi+1−bi)Ai=n12n(n+1)−i=1∑n−1(i+11−i1)2i(i+1)(m−11−m1)2m(m−1)=m−1⋅mm−m−1⋅2m(m−1)=2m(m−1)(m−m−1)=2(m+m−1)m(m−1)由基本不等式a+bab≤4a+b得到：(m−11−m1)2m(m−1)≤8m+m−1因此：=n12n(n+1)−i=1∑n−1(i+11−i1)2i(i+1)=n12n(n+1)+i=1∑n−1(i1−i+11)2i(i+1)<2n+1n+81(1+2+2++3+3+⋯+n−1+n−1+n)=2n+1n+81(2S−1−n)整理得：S<6(4n+3)n−1<6(4n+3)n右侧不等式得证，而且得到更精细的不等式。
三、一些算法题的式子优化
3.1 3500.将数组分割为子数组的最小代价
原题链接
3500. 将数组分割为子数组的最小代价
思路分析
对于 第 i 个子数组nums[l…r]的和我们记为 t(i)，cost[l…r] 的和我们记为 B(i)
那么 第 i 个子数组的收益为：t(i) * B(i) + k * i * B(i)
如果只有前半部分或者 后半部分没有i，那么我们可以轻松的写出 O(N^2) 的 划分型dp
但是现在有 i，考虑对后半部分Abel 变换：
∑ i = 1 k i B ( i ) = k S ( i ) − ∑ i = 1 k − 1 S ( i ) = S ( i ) + S ( i ) − S ( 1 ) + S ( i ) − S ( 2 ) + . . . + S ( i ) − S ( i − 1 ) 其中， S ( i ) 为前 i 个 c o s t 子数组的和 \begin{align} & \sum_{i=1}^{k} iB(i) \\ &= kS(i) - \sum_{i=1}^{k-1} S(i) \\ &= S(i) + S(i) - S(1) + S(i) - S(2) + ... + S(i) - S(i-1) \\ & 其中，S(i) 为 前i个cost子数组的和 \end{align} i=1∑kiB(i)=kS(i)−i=1∑k−1S(i)=S(i)+S(i)−S(1)+S(i)−S(2)+...+S(i)−S(i−1)其中，S(i)为前i个cost子数组的和
我们发现 k 个子数组的 后半部分贡献就是 k 个cost[] 的后缀和
如果我们记 f(i + 1) 为下标[0,i] 分割后的最小总代价，则有如下转移：
f [ i + 1 ] = min j = 0 i f [ j ] + ( t [ i ] − t [ j ] ) × ( s [ i ] − s [ j ] ) + k × ( s [ n ] − s [ i ] ) \begin{align} f[i + 1] = \min_{j=0}^{i} f[j] + (t[i] - t[j]) \times (s[i] - s[j]) + k \times (s[n] - s[i]) \end{align} f[i+1]=j=0minif[j]+(t[i]−t[j])×(s[i]−s[j])+k×(s[n]−s[i])
时间复杂度：O(N^2)
可用凸包优化至 O(N)
AC代码
using i64 = long long;class Solution {
static constexpr i64 inf = 1E18;
public:i64 minimumCost(std::vector<int>& nums, std::vector<int>& cost, int k) {int n = nums.size();std::vector<int> s(n + 1);for (int i = 1; i <= n; ++ i) s[i] = cost[i - 1] + s[i - 1];std::vector<i64> f(n + 1, inf);f[0] = 0;int t = 0;for (int i = 1; i <= n; ++ i) {t += nums[i - 1];for (int j = 0; j < i; ++ j) {f[i] = std::min(f[i], f[j] + 1LL * t * (s[i] - s[j]) + k * (s[n] - s[j]));}}return f[n];}
};
3.2 D. Array Splitting
原题链接
D. Array Splitting
思路分析
我们要最大化 Σ ai f(i)
对式子进行Abel 变换：
∑ i = 1 n a i f ( i ) = A ( n ) f ( n ) − ∑ i = 1 n − 1 [ f ( i + 1 ) − f ( i ) ] A ( i ) = k A ( n ) − ∑ i = 1 n − 1 [ f ( i + 1 ) − f ( i ) ] A ( i ) \begin{align} & \sum_{i=1}^{n}a_if_(i) \\ &= A(n)f(n) - \sum_{i=1}^{n-1}[f(i+1)-f(i)]A(i)\\ &= kA(n) - \sum_{i=1}^{n-1}[f(i+1)-f(i)]A(i) \end{align} i=1∑naif(i)=A(n)f(n)−i=1∑n−1[f(i+1)−f(i)]A(i)=kA(n)−i=1∑n−1[f(i+1)−f(i)]A(i)
注意到 f(i + 1) - f(i) 可能的取值只有1 / 0，并且只会在每组的分段点处取一次1，一共会取k - 1次
为了让结果尽可能大，我们要让减去的部分尽可能的小，也就是说我们要选前k - 1 小的 A(i)，即 前k - 1 小的前缀和
于是我们先把 kA(n) 累加到答案中，然后对前缀和数组去除A(n)后，减去前k - 1小A(i)
时间复杂度：O(n)，C++快速划分的时间复杂度为O(N)
AC代码
#include <bits/stdc++.h>
using i64 = long long;int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int n, k;std::cin >> n >> k;std::vector<i64> A(n);for (int i = 0; i < n; ++ i) {std::cin >> A[i];if (i > 0) A[i] += A[i - 1];}i64 ans = A[n - 1] * k;A.pop_back();std::ranges::sort(A);ans -= std::reduce(A.begin(), A.begin() + k - 1);std::cout << ans << '\n';return 0;
}
3.3 300. 任务安排1
原题链接
300. 任务安排1
思路分析
和 3.1 类似，我们先想一个 O(N^3) 的暴力dp：
定义 f(i, j) 为 前 i 个任务划分 j 组的最小费用，则有如下转移：
- 记 T[i] 为 前 i 个任务的时间和
- A[i] 为 第 i 批任务的 c[] 之和，B[i] 为 前 i 批任务的 c[] 之和
- C[i] 为 前 i 个任务的 c[] 之和
f ( i , j ) = min k = 1 i − 1 f ( k , j − 1 ) + A [ j ] × ( T [ i ] + j S ) = min k = 1 i − 1 f ( k , j − 1 ) + A [ j ] T [ i ] + A [ j ] j S \begin{align} & f(i, j) = \min_{k=1}^{i-1} f(k, j-1) + A[j] \times (T[i] + jS) \\ &= \min_{k=1}^{i-1} f(k, j-1) + A[j]T[i] + A[j]jS \\ \end{align} f(i,j)=k=1mini−1f(k,j−1)+A[j]×(T[i]+jS)=k=1mini−1f(k,j−1)+A[j]T[i]+A[j]jS
我们发现如果最后一项没有j，那么就是O(N^2)的dp
考虑对最后一项进行 Abel 变换：
∑ i = 1 k A [ i ] i S = B [ k ] k S − ∑ i = 1 k − 1 S B [ i ] = B [ k ] S + B [ k ] S − B [ k − 1 ] S + . . . + B [ 2 ] S − B [ 1 ] S 拆成了 k 个后缀和 \begin{align} & \sum_{i=1}^{k}A[i]iS \\ &= B[k]kS - \sum_{i=1}^{k-1}SB[i]\\ &= B[k]S + B[k]S - B[k - 1]S + ... + B[2]S - B[1]S \\ & 拆成了 k 个后缀和 \end{align} i=1∑kA[i]iS=B[k]kS−i=1∑k−1SB[i]=B[k]S+B[k]S−B[k−1]S+...+B[2]S−B[1]S拆成了k个后缀和
则我们定义 f(i + 1) 为 对下标 [0, i] 分组后的最小花费，有如下转移方程：
f [ i ] = min j = 0 i − 1 f [ j ] + ( C [ i ] − C [ j ] ) × T [ i ] + s × ( C [ n ] − C [ j ] ) \begin{align} & f[i] = \min_{j=0}^{i - 1} f[j] + (C[i] - C[j]) \times T[i] + s \times (C[n] - C[j]) \end{align} f[i]=j=0mini−1f[j]+(C[i]−C[j])×T[i]+s×(C[n]−C[j])
时间复杂度：O(N^2)
可凸包优化
AC代码
#include <bits/stdc++.h>
using i64 = long long;constexpr i64 inf = 1E18;int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int n, s;std::cin >> n >> s;std::vector<int> t(n), c(n);for (int i = 0; i < n; ++ i) {std::cin >> t[i] >> c[i];}std::vector<i64> T(n + 1), C(n + 1);for (int i = 1; i <= n; ++ i) {T[i] = T[i - 1] + t[i - 1];C[i] = C[i - 1] + c[i - 1];}std::vector<i64> f(n + 1, inf);f[0] = 0;for (int i = 1; i <= n; ++ i) {for (int j = 0; j < i; ++ j) {f[i] = std::min(f[i], f[j] + (C[i] - C[j]) * T[i] + s * (C[n] - C[j]));}}std::cout << f[n] << '\n';return 0;
}