【前缀和与差分】知识点理解
题目描述
输入一个长度为n的整数序列。
接下来输入m个操作,每个操作包含三个整数l, r, c,表示将序列中[l, r]之间的每个数加上c。
请你输出进行完所有操作后的序列。
第一行包含两个整数n和m。
第二行包含n个整数,表示整数序列。
接下来m行,每行包含三个整数l,r,c,表示一个操作。
样例
6 3
1 2 2 1 2 1
1 3 1
3 5 1
1 6 1
3 4 5 3 4 2
知识点
-
知识点1:差分与前缀和是一组相反的操作,假设给定一个数组 A ,其前缀和数组表示A[i]及其之前所有数的和。其差分数组则表示该数组的前缀和为A[i]即假设B的前缀和数组为A,则A的差分数组是B。
-
知识点2:假设给定一个数组 A ,其差分数组为 B, 如果对A数组的某个区间 [l, r]上每个数都加一个数c, 其等价于 B 数组中 B[l] += c,且 B[r + 1] -=c。因为A[l]表示B[l]的前缀和,则如果B[l]多加一个c(B[l] += c),则A[l], A[l+1], …, A[r], A[r + 1], …, A[n] 都将多加一个c。而我们只需要 [l, r] 上加c,所以对于 A 在 [r+1, n]区间上的值再减去 c,即对应于 B[r + 1] -= c。
-
知识点3:在初始化时,我们可以理解为在0数组上,依次插入一个c = A[i],则只需要对差分数组执行 B[i] += A[i], B[i + 1] -= A[i]即可
-
知识点4:最终所有m个操作后,得到的是对差分数组B的操作,分别求其各个位置的前缀和即得到A数组
-
知识点5:本题其实可以直接按照原始的方法,依次遍历 A 数组的 [l, r] 区间,并执行 A[i] += c,但每次的操作的时间复杂度都是O(n),使用差分数组,则可以将每次操作转换为一个公式即可,即时间复杂度变为 O(1)。更直观的来说,修改前缀和的某个连续区间范围内的值,可以转化为其差分数组的某两个值
C++ 代码
#include <iostream>
using namespace std;
const int N = 1e5 + 5;
int n, m;
int A[N], B[N];
int fun(int l, int r, int c) {
B[l] += c;
B[r + 1] -= c;
}
int main() {
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i ++) scanf("%d", &A[i]);
for(int i = 1; i <= n; i ++) fun(i, i, A[i]); // 相当于在区间 [i, i] 上多加一个 A[i]
while(m --) {
int l, r, c;
scanf("%d%d%d", &l, &r, &c);
fun(l, r, c); // 相当于在 [l, r] 上多加一个 c
}
// 经过操作后,可以通过前缀和得到A数组
for(int i = 1; i <= n; i ++) A[i] = A[i - 1] + B[i], printf("%d ", A[i]);
return 0;
}