一、差分
前缀和与差分的核心思想是预处理,能在暴力枚举过程中快速给出查询结果,从而优化时间复杂度。这是经典的用空间换时间的做法。
本质:前缀和与差分是一对互逆的运算。
二、一维差分
2.1 差分数组构建方式
基于定义:f[i] = a[i] - a[i-1]
基于性质(用于区间更新):f[L] += c, f[R+1] -= c
2.2 根据差分数组的性质处理区间修改
核心逻辑是在区间起点增加数值,在终点后一位减少数值。这样在进行前缀和还原时,中间段都会受到影响,而区间外不受影响。
2.3 还原数组
对差分数组做一次「前缀和」,即可还原出原数组。
三、一维差分经典算法题
3.1【模板】差分
题目描述
给定一个长度为 n 的数列,每次操作将区间 [l, r] 内的数都加上 k,最后输出整个数列。
算法原理
依照一维差分原理模拟即可。先通过初始数组构建差分数组,再执行区间修改,最后还原。
代码实现
方法一:直接利用差分数组性质
#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int n, m;
int f[N];
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
f[i] += x;
f[i + 1] -= x;
}
while (m--) {
int l, r, k;
cin >> l >> r >> k;
f[l] += k;
f[r + 1] -= k;
}
for (int i = 1; i <= n; i++) {
f[i] += f[i - 1];
cout << f[i] << " ";
}
return 0;
}


