一、前缀和

1. 一维前缀和

定义：前缀和数组 s[i] 表示原数组 a[] 前 i 项的和
公式：

s[i] = s[i-1] + a[i]  

应用：快速计算区间 [l, r] 的和

sum = s[r] - s[l-1]

2. 二维前缀和

定义：s[i][j] 表示从左上角 (1,1) 到 (i,j) 的子矩阵和
公式：

s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j]

应用：快速计算子矩阵 (x1,y1)-(x2,y2) 的和

sum = s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1]

---

二、差分

1. 一维差分

定义：差分数组 b[i] 是原数组 a[] 相邻元素的差值
公式：

b[i] = a[i] - a[i-1]  // 注意方向（非 a[i-1] - a[i]）

核心操作：

• 对区间 [l, r] 增加 c：

b[l] += c
b[r+1] -= c  // 注意越界保护

2. 差分重建原数组

公式：

a[i] = a[i-1] + b[i]  // 通过前缀和还原

---

三、代码实现对比

// 差分操作核心代码（已修复）
#include <iostream>  // 避免用<bits/stdc++.h>
using namespace std;
const int maxn = 1001;
int a[maxn], diff[maxn]; // 更清晰的变量名

int main() {
    int n, l, r, c;
    cin >> n;
    for(int i=1; i<=n; i++) cin >> a[i];

    // 正确构造差分数组
    for(int i=1; i<=n; i++) {
        diff[i] = a[i] - a[i-1]; // 非 a[i+1]-a[i]
    }

    cin >> l >> r >> c;
    diff[l] += c;
    if(r+1 <= n) diff[r+1] -= c; // 防止越界

    // 重建数组
    for(int i=1; i<=n; i++) {
        a[i] = a[i-1] + diff[i];
    }

    // 输出结果
    for(int i=1; i<=n; i++) {
        cout << a[i] << " "; // 添加空格分隔
    }
    return 0;
}

---

四、常见错误总结

错误类型	修正方案
差分方向错误	b[i] = a[i] - a[i-1]
数组越界访问	增加 if(r+1 <= n) 保护
二维公式下标错误	严格检查 i-1 和 j-1 的对称性
未初始化边界值	确保 a[0] = 0, s[0][0] = 0

---

五、应用场景对比

算法	时间复杂度	典型应用场景
前缀和	预处理 O(n)，查询 O(1)	频繁区间求和
差分	预处理 O(n)，操作 O(1)	多次区间增减后单次重建数组

---