前缀和差分【算法 13】

在算法领域中，前缀和与差分数组是两种高效处理区间问题的技术。它们能在特定问题场景下将时间复杂度从 (O(n)) 降到 (O(1))，适用于频繁的区间查询与修改操作。本文将简要介绍这两种技术及其应用。
请添加图片描述

1. 前缀和 (Prefix Sum)

前缀和是指一个数组的第 (i) 个前缀和为原数组前 (i) 个元素之和。通过构建前缀和数组，我们可以高效地进行区间求和。

前缀和公式：

设原数组为 (A)，前缀和数组为 (P)，那么：
$P [i] = A [1] + A [2] + ... + A [i]$
利用前缀和，可以快速计算任意区间 ([l, r]) 的和：
$\text{sum}(l, r) = P[r] - P[l-1]$

这种方法将单次区间求和的时间复杂度从 (O(n)) 降到 (O(1))，而构建前缀和数组的时间复杂度为 (O(n))。

示例代码：

void buildPrefixSum(int A[], int P[], int n) {P[0] = A[0];for (int i = 1; i < n; i++) {P[i] = P[i-1] + A[i];}
}int querySum(int P[], int l, int r) {return l == 0 ? P[r] : P[r] - P[l-1];
}

应用场景：

频繁的区间和查询，例如在区间内求和、计算连续子数组的和等。

2. 差分数组 (Difference Array)

差分数组是一种高效处理区间修改的工具。差分数组的核心思想是记录变化，而不是直接修改原数组。通过构造一个差分数组，可以在 (O(1)) 时间内对原数组的一个区间进行增量更新。

差分数组公式：

设原数组为 (A)，差分数组为 (D)，那么：
$D [i] = A [i] - A [i - 1]$

通过差分数组，我们可以对区间 ([l, r]) 进行增量修改，假设增加值为 (x)，则：
$D [l] + = x$

$D [r + 1] - = x$

最后，通过构建最终的数组，我们可以恢复修改后的原数组。

示例代码：

void buildDifferenceArray(int A[], int D[], int n) {D[0] = A[0];for (int i = 1; i < n; i++) {D[i] = A[i] - A[i-1];}
}void updateRange(int D[], int l, int r, int x) {D[l] += x;if (r + 1 < n) {D[r + 1] -= x;}
}void applyDifferenceArray(int A[], int D[], int n) {A[0] = D[0];for (int i = 1; i < n; i++) {A[i] = A[i-1] + D[i];}
}