前缀和与差分简介

前缀和与差分是处理数组问题时最基础、最强大的两种预处理思想。它们互为逆运算，一个为“区间查询”而生，一个为“区间修改”而生，共同构成了处理静态数组问题的基石。

前缀和的核心思想是 “用空间换时间”。我们通过一次性的预处理，创建一个辅助数组，记录下原始数组从开头到当前位置的累计和。这个“记总账”的行为，使得后续任意区间的求和查询都可以在瞬间完成。

a. 构建前缀和数组 prefix
创建一个比原始数组 a 长度多 1 的 prefix 数组，并令 prefix[0] = 0（这个“哨兵”可以简化查询逻辑）。
prefix[i] 存储的是 a[0] 到 a[i-1] 的和。

// 原始数组 a = {a_0, a_1, ..., a_{n-1}}
std::vector<long long> prefix(n + 1, 0);
for (int i = 0; i < n; ++i) {
    prefix[i + 1] = prefix[i] + a[i];
}

b. 进行区间查询
要计算原始数组 a 在闭区间 [l, r] 的和，使用以下公式：

sum(l, r) = prefix[r + 1] - prefix[l]

差分是前缀和的逆运算，它的核心思想是 “延迟计算” 和 “影响标记”。它不记录每个元素的具体值，而是记录当前元素与前一个元素的差值。通过这种方式，对一个区间的整体增减操作，可以巧妙地转化为只对区间两个端点的“影响标记”进行修改。

a. 构建差分数组 diff
diff[i] 存储的是 a[i] - a[i-1]（规定 a[-1]=0）。

// 原始数组 a = {a_0, a_1, ..., a_{n-1}}
std::vector<int> diff(n);
diff[0] = a[0];
for (int i = 1; i < n; ++i) {
    diff[i] = a[i] - a[i-1];
}

b. 进行区间修改
要给原始数组 a 的闭区间 [l, r] 上的每个元素都加上 value，只需修改差分数组的两个位置：

diff[l] += value;
if (r + 1 < n) {
    diff[r + 1] -= value;
}

第一个操作 diff[l] += value 使得从 l 开始的所有元素在求前缀和时都会增加 value。第二个操作则是在 r+1 的位置把这个影响抵消掉，保证修改只在 [l, r] 区间内生效。

c. 还原最终数组
在完成所有修改后，如果需要得到最终的数组 a，只需对差分数组 diff 求一次前缀和即可。

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

查询低效：在完成所有 O(1) 的修改后，如果想查询任何一个位置或区间的具体值，都必须先花费 O(N) 的时间对差分数组求前缀和来还原整个数组。