当前位置：首页 > news >正文

【一维前缀和+差分】

news 2025/7/15 13:29:36

一、一维前缀和

1.1 定义

给定一个数组 a[1..n]，其前缀和数组 pre[1..n] 定义为：

$\dots + a[i]$

即 pre[i] 表示原数组从第 1 项到第 i 项的和。

1.2 构建

int a[N], pre[N];
for (int i = 1; i <= n; i++) 
{pre[i] = pre[i - 1] + a[i];
}

1.3 区间求和

使用前缀和可以在 $O (1)$ 时间内求任意区间 $[l, r]$ 的和：

$s u m = p re [r] - p re [l - 1]$

公式推导：

$\dots + a[l-1] + a[l] + \dots + a[r] \\ pre[l-1] = a[1] + a[2] + \dots + a[l-1]$

所以两者一减，刚好剩下区间 $[l, r]$ 的和。

1.4 应用场景

快速计算区间和
优化暴力 $O(n^2)$ 的区间统计问题为 $O (n)$

1.5 示例

// 输入一个数组，求多个区间 [l, r] 的和
int a[N], pre[N];
cin >> n >> q;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) pre[i] = pre[i - 1] + a[i];while (q--) 
{int l, r;cin >> l >> r;cout << pre[r] - pre[l - 1] << '\n';
}

二、一维差分数组

2.1 定义

对于原数组 a[1..n]，其差分数组 diff[1..n] 定义为：

$1]\ \ (i \geq 2),\ \ diff[1] = a[1]$

2.2 构建

int a[N], diff[N];
diff[1] = a[1];
for (int i = 2; i <= n; i++) 
{diff[i] = a[i] - a[i - 1];
}

2.3 区间加法操作

若想对区间 $[l, r]$ 所有数加上 $d$ ，只需：

diff[l] += d;
diff[r + 1] -= d;

原理在于：差分数组记录的是“增量”，只需要在区间起点加一个数、在区间终点的下一位减去这个数，就能确保中间所有位置都累加这个值。

然后通过前缀和还原整个数组：

a[1] = diff[1];
for (int i = 2; i <= n; i++) 
{a[i] = a[i - 1] + diff[i];
}

2.4 区间减法操作

若想对区间 $[l, r]$ 所有数减去 $d$ ，也可以使用差分数组：

diff[l] -= d;
diff[r + 1] += d;

原理类似：差分数组记录的是“增量”，如果我们想对一个区间 $[l, r]$ 的所有元素减去 $d$ ，只需要在区间起点加上 $- d$ ，在区间终点的下一位加上 $+ d$ ，就能确保整个区间内的值都减少 $d$ ，而其他位置不受影响。这与区间加法操作完全对称，只是将 $d$ 替换为 $- d$ 。

三、差分原理

3.1 目的

差分数组的核心目的是：将原本需要 O(n) 的区间修改操作优化为 O(1)。

比如：我们想对数组中一段区间 $[l, r]$ 的所有元素都加上一个数 $d$ ，若用原数组暴力加法，每次操作就要 $O (r - l + 1)$ ；当有 $m$ 次操作时，总复杂度是 $O (mn)$ ，会超时。

3.2 差分数组的构建

我们构建一个数组 $\ldots n]$ ：

$d i ff [i] = a [i] - a [i - 1]$

也可以理解为：

差分数组记录的是原数组中相邻两项之间的“变化量”。

根据这个定义，有：

$\dots + diff[i] \Rightarrow a[i] = \sum_{j=1}^{i} diff[j]$

也就是说，原数组可以通过差分数组做前缀和来还原。

3.3 差分操作的核心逻辑

想要将区间 $[l, r]$ 所有数都加上 $d$ ，我们可以在 diff[] 上做如下处理：

diff[l] += d;
diff[r + 1] -= d;

为什么这样就能完成整个区间的加法？

我们回忆差分的“还原”过程：

a[1] = diff[1];
a[2] = a[1] + diff[2];
a[3] = a[2] + diff[3];
...

你会发现，前缀相加会让 diff[l] 的影响一直传导下去。直到 diff[r+1] 把这部分影响抵消为止。

也就是说：

$a [l]$ 到 $a [r]$ 都被加上了 $d$
而 $a [r + 1]$ 之后的数不受影响

这就实现了：O(1) 修改一个区间

四、一个形象的类比

假设你站在楼梯上，从第 1 级楼梯往上走，a[i] 是你在第 i 级台阶上的高度。

前缀和：相当于你每走一步都记一下总共走了多远。
差分数组：相当于你记录每一步你上升（或下降）了多少。

你只要知道每一步的变化量（差分数组），就能还原出每一级台阶的实际高度（原数组）；你也能知道在一段范围内你升高了多少（前缀和）。

五、前缀和与差分的区别与联系

类别	作用	技术本质	时间复杂度
前缀和	快速查询区间和	把每个位置存成前缀累加和	查询 $O (1)$ ，构建 $O (n)$
差分数组	快速区间修改	存储相邻值之间的“变化”	修改 $O (1)$ ，恢复 $O (n)$