一维前缀和
前缀和：数组不变，多次区间求和 → O(1) 查询。差分：多次区间加减，最后查结果 → O(1) 修改。
// 构建（1-based，s[0]=0 处理边界；和可能爆 int 换 long）int n = a.length;long[] s = new long[n + 1];for (int i = 0; i < n; i++) { s[i + 1] = s[i] + a[i];} // 查询 [l, r]（1-based）long ans = s[r] - s[l - 1];若题目 0-based，区间 [l, r] 答案是
s[r+1] - s[l]。
二维前缀和
构建：
prefix[i+1][j+1] = matrix[i][j] + prefix[i][j+1] + prefix[i+1][j] - prefix[i][j]
查询：
sum = prefix[row2+1][col2+1] - prefix[row1][col2+1] - prefix[row2+1][col1] + prefix[row1][col1]
// 构建 (m+1)×(n+1)，下标从 1 开始int m = grid.length, n = grid[0].length;long[][] s = new long[m + 1][n + 1];for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + grid[i-1][j-1]; }} // 查询左上(r1,c1)到右下(r2,c2)，0-based输入转1-basedlong ans = s[r2+1][c2+1] - s[r1][c2+1] - s[r2+1][c1] + s[r1][c1];口诀：构建 = 左+上−左上+自己；查询 = 右下−左−上+左上。
一维差分
识别信号：多次区间 [l, r] += v，最后查整组结果。
long[] b = new long[n + 2]; // 多开 2 防越界 void insert(int l, int r, long v) { // l, r 为 1-based b[l] += v; b[r + 1] -= v;} // 还原成原数组（原地前缀和）for (int i = 1; i <= n; i++) { b[i] += b[i - 1];}左闭右开区间（如车上下客）需把 r 换成 r-1。
二维差分
识别信号：多次子矩阵区域 += v，最后查整组结果。
一维差分用两点标记区间，二维差分用四点标记子矩阵。下面用一个具体例子对照上图，一步步拆解累加原理。
上图分左右两栏。左栏是标记阶段，在 5×5 矩阵上对目标子矩阵 (2,2)→(3,4) 加 1，diff 数组只有四个格子非零。右栏是还原阶段，跑完二维前缀和后 +1 刚好填满目标区域，其余位置为 0。
第 1 步：放源头。 在 diff[2][2] 放 +1。它会在前缀和中向右下方向传播，覆盖 [2..5] × [2..5] 整个右下区域——此时第 2,3,4,5 行 × 第 2,3,4,5 列都会变成 1。显然多出来了，需要截断。
![第 1 步：diff2 的 +1 向右下传播
第 2 步：截断右侧。 在 diff[2][5] 放 -1（对应 y2+1=5）。前缀和中，-1 从 (2,5) 开始向右下传播，把第 5 列及右侧多出来的 1 抵消掉。此时受影响区域缩小为 [2..5] × [2..4]。
![第 2 步：diff 的 -1 抵消第 5 列及右侧
第 3 步：截断下侧。 在 diff[4][2] 放 -1（对应 x2+1=4）。前缀和中，-1 从 (4,2) 开始向右下传播，把第 4、5 行多出来的 1 抵消掉。此时受影响区域缩小为 [2..3] × [2..4]。
第 4 步：补回右下角。 前两步截断在右下角 (4,5) 处重叠——两次 -1 在此处形成 -2，多扣了一个 1。所以在 diff[4][5] 放 +1 补回来。至此，跑完二维前缀和后，+1 精确覆盖 [2..3] × [2..4]，恰好是目标子矩阵。
long[][] diff = new long[m + 2][n + 2]; void insert(int x1, int y1, int x2, int y2, long v) { diff[x1][y1] += v; diff[x1][y2 + 1] -= v; diff[x2 + 1][y1] -= v; diff[x2 + 1][y2 + 1] += v;} // 还原（二维前缀和）for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { diff[i][j] += diff[i-1][j] + diff[i][j-1] - diff[i-1][j-1]; }}本文由 AgentPlanFlow 生成