离散化Prefix
Part 1: 二维前缀和 (2D Prefix Sum)
1. 问题场景
想象一下，你有一个二维的矩阵（比如一张像素图），现在频繁地问你：“请告诉我，从左上角 (r1, c1) 到右下角 (r2, c2) 这个子矩阵里，所有元素的和是多少？”
暴力解法： 太直接了。来一个查询，我就写一个二重循环，从 r1 遍历到 r2，从 c1 遍历到 c2，把所有数加起来。
// 暴力解法
int query_brute_force(int[][] matrix, int r1, int c1, int r2, int c2) {
int sum = 0;
for (int i = r1; i <= r2; i++) {
for (int j = c1; j <= c2; j++) {
sum += matrix[i][j];
}
}
return sum;
}
复杂度分析：如果矩阵是 N x M，一个查询的复杂度最坏是 O(N M)。Q 次查询就是 O(Q N * M)，这在数据量大的时候是不可接受的。
思路演进： 一维的问题，我们用前缀和把 O(N) 的区间求和优化到了 O(1)。二维的能不能也这么干？当然可以！
2. 二维前缀和的原理
我们定义一个二维前缀和数组 sum[][]。sum[i][j] 存的是什么呢？它存的是从左上角 (0, 0) 到当前位置 (i, j) 这个矩形区域内所有元素的和。
怎么计算这个 sum[i][j] 呢？这里要用到一个非常经典的思想——容斥原理。
看图说话： 为了计算 sum[i][j]（整个蓝色+绿色的区域），我们可以：
拿它上面那个矩形的和
sum[i-1][j](区域1+区域2)。加上它左边那个矩形的和
sum[i][j-1](区域1+区域3)。这时你会发现，左上角的那个小矩形
sum[i-1][j-1](区域1) 被加了两遍！所以要减掉一次。最后，别忘了加上当前位置
matrix[i][j](区域4) 本身的值。
于是，我们得到了二维前缀和的递推公式： sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + matrix[i][j]
如何查询？ 有了这个 sum 数组，怎么求 (r1, c1) 到 (r2, c2) 的和呢？还是用容斥原理！
先取右下角为
(r2, c2)的大矩形sum[r2][c2]。减掉它上面多余的部分，也就是
sum[r1-1][c2]。减掉它左边多余的部分，也就是
sum[r2][c1-1]。你会发现，左上角
sum[r1-1][c1-1]这块区域，被减了两次，所以要加回来一次。
于是，我们得到了查询公式： query(r1, c1, r2, c2) = sum[r2][c2] - sum[r1-1][c2] - sum[r2][c1-1] + sum[r1-1][c1-1]
这样，预处理的复杂度是 O(N * M)，但每次查询都变成了 O(1)！
3. OI/ACM 风格代码实现 (LeetCode 304)
代码技巧：为了避免处理 i-1 或 j-1 时烦人的边界判断，我们通常把前缀和数组 sum 的尺寸定义为 (N+1) x (M+1)，让它的下标从 1 开始。这样 sum[0][j] 和 sum[i][0] 天然就是 0，公式就统一了。
class NumMatrix {
private int[][] sum; // 1-based indexing prefix sum array
public NumMatrix(int[][] matrix) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return;
}
int rows = matrix.length;
int cols = matrix[0].length;
// 使用 (rows+1) x (cols+1) 的尺寸，避免边界判断
sum = new int[rows + 1][cols + 1];
// 构建二维前缀和数组
for (int i = 1; i <= rows; i++) {
for (int j = 1; j <= cols; j++) {
// sum[i][j] 对应 matrix[i-1][j-1]
sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + matrix[i - 1][j - 1];
}
}
}
public int sumRegion(int row1, int col1, int row2, int col2) {
// 传入的坐标是 0-based，我们的 sum 数组是 1-based
// 所以查询时坐标要 +1
int r1 = row1 + 1;
int c1 = col1 + 1;
int r2 = row2 + 1;
int c2 = col2 + 1;
// 应用查询公式
return sum[r2][c2] - sum[r1 - 1][c2] - sum[r2][c1 - 1] + sum[r1 - 1][c1 - 1];
}
}
Part 2: 二维差分 (2D Difference Array)
1. 问题场景
与前缀和相反，现在我们要做的是区域更新。 指令：“请把矩阵中，从 (r1, c1) 到 (r2, c2) 这个子矩阵里，所有元素都加上一个值 val”。 做完所有 M 次更新后，请告诉我最终的矩阵是什么样子。
暴力解法：来一次更新，我就二重循环遍历 (r1, c1) 到 (r2, c2)，挨个加上 val。复杂度 O(M * N²)。
思路演进： 一维差分能把区间更新变成 O(1) 的边界点修改。二维差分也一样！ 我们定义一个二维差分数组 diff[][]。它和原矩阵 matrix 的关系是：matrix 是 diff 的二维前缀和。
那么，对 matrix 的一个子矩阵 (r1, c1) -> (r2, c2) 全体 +val，会对 diff 产生什么影响？ 我们逆向思考前缀和的查询公式。我们希望在 (r1, c1) 这个点开始，之后的所有点（通过前缀和累加）都获得一个 +val 的效果。
我们在
diff[r1][c1]加上val。这会导致(r1, c1)右下方的所有点在前缀和计算后都增加了val。但是，这个影响超出了我们想要的
c2列。为了消除c2列之后的影响，我们需要在diff[r1][c2+1]减去val。同理，这个影响也超出了我们想要的
r2行。为了消除r2行之后的影响，我们需要在diff[r2+1][c1]减去val。这样一来，对于
(r2+1, c2+1)右下方的区域，我们既减了一次（来自2），又减了一次（来自3），多减了一次！所以要把它加回来，在diff[r2+1][c2+1]加上val。
结论（核心）： 对原矩阵 (r1, c1) -> (r2, c2) 的区间执行 +val 操作，等价于对它的差分数组 diff 执行四个单点操作：
diff[r1][c1] += valdiff[r1][c2+1] -= valdiff[r2+1][c1] -= valdiff[r2+1][c2+1] += val
O(N²) 的区域更新，又变成了 O(1) 的四次定点修改！
2. 代码实现与相关题目
场景题：比如 "地毯铺设" 问题 (洛谷 P3397)。在一个 n x n 的场地上，铺了 m 块矩形地毯，求最后每个点被多少层地毯覆盖。 这不就是每铺一块地毯，就对一个矩形区域 +1 吗？典型的二维差分。
public class TwoDimDifference {
private int[][] diff;
private int rows, cols;
public TwoDimDifference(int rows, int cols) {
this.rows = rows;
this.cols = cols;
// 差分数组要开大一点，防止 c2+1 或 r2+1 越界
this.diff = new int[rows + 2][cols + 2];
}
/**
* 对 (r1, c1) -> (r2, c2) 区域增加 val
* @param r1, c1, r2, c2 (0-based index)
*/
public void update(int r1, int c1, int r2, int c2, int val) {
// 转换为 1-based indexing for diff array
int x1 = r1 + 1, y1 = c1 + 1;
int x2 = r2 + 1, y2 = c2 + 1;
diff[x1][y1] += val;
diff[x1][y2 + 1] -= val;
diff[x2 + 1][y1] -= val;
diff[x2 + 1][y2 + 1] += val;
}
/**
* 从差分数组还原出最终的矩阵
* @return 最终结果矩阵
*/
public int[][] recover() {
int[][] result = new int[rows][cols];
// 临时前缀和数组
int[][] prefixSum = new int[rows + 2][cols + 2];
for (int i = 1; i <= rows; i++) {
for (int j = 1; j <= cols; j++) {
prefixSum[i][j] = prefixSum[i - 1][j] + prefixSum[i][j - 1] - prefixSum[i - 1][j - 1] + diff[i][j];
result[i - 1][j - 1] = prefixSum[i][j];
}
}
return result;
}
}
Part 3: 离散化 (Discretization)
1. 问题场景
想象一个更变态的问题：一条无限长的公路（坐标范围 1 到 10^9）。现在有 N (N <= 10^5) 个施工队，第 i 个队伍要对 [L_i, R_i] 这段路进行施工（比如，把路的高度都增加1）。问所有施工队都完工后，公路上哪个点的施工层数最多？
分析： 这不就是我们前面讲的一维差分吗？diff[L_i]++, diff[R_i+1]--。 问题是：坐标范围是 10^9！你敢开一个大小为 10^9 的差分数组吗？内存直接爆炸。
思路演进： 我们真的关心 1 到 10^9 之间的每一个点吗？不关心！ 我们只关心那些施工区间的端点，比如 L_i 和 R_i+1。因为在两个相邻的端点之间，施工的层数是不变的。
比如说，有施工 [100, 200] 和 [150, 800]。 有意义的坐标点就是 100, 150, 200+1=201, 800+1=801。 我们真正关心的区间是：[100, 149], [150, 200], [201, 800], [801, ...]。 这些稀疏、巨大的坐标，我们可以把它们“压缩”到连续的、小的整数索引上，比如 0, 1, 2, 3 ...。这个过程，就叫离散化。
2. 离散化的步骤与实现
用一个具体题目来说明：酒店预订问题 AcWing 802. 区间和 (这是一个经典的离散化+前缀和/差分模板题) 问题：有 n 次操作，每次操作是给 x 位置加上 c。有 m 次查询，每次查询 [l, r] 区间的和。x, l, r 范围很大。
离散化步骤：
收集所有坐标：把所有操作和查询中涉及到的坐标
x, l, r全部收集到一个列表里。排序并去重：对这个列表进行排序和去重，得到一个有序的、无重复的坐标轴。
建立映射：创建一个
HashMap，建立从“原始大坐标”到“离散化后的小索引”的映射关系。map.put(原始坐标, 0),map.put(下一个原始坐标, 1)...在小索引上操作：现在，我们可以在一个大小等于去重后坐标数量的小数组上，执行我们的算法（比如前缀和）。
add(x, c)操作，变成在a[map.get(x)] += c。query(l, r)操作，需要找到l和r在离散化坐标轴上的位置，然后求和。
代码实现 (以离散化+前缀和为例)
import java.util.*;
public class DiscretizationExample {
// 假设这是输入
static class AddOp { int x, c; AddOp(int x, int c){this.x=x;this.c=c;} }
static class QueryOp { int l, r; QueryOp(int l, int r){this.l=l;this.r=r;} }
public static void solve(List<AddOp> adds, List<QueryOp> queries) {
// 1. 收集所有坐标
List<Integer> allCoords = new ArrayList<>();
for (AddOp op : adds) {
allCoords.add(op.x);
}
for (QueryOp op : queries) {
allCoords.add(op.l);
allCoords.add(op.r);
}
// 2. 排序并去重
Collections.sort(allCoords);
List<Integer> uniqueCoords = new ArrayList<>();
if (!allCoords.isEmpty()) {
uniqueCoords.add(allCoords.get(0));
for (int i = 1; i < allCoords.size(); i++) {
if (!allCoords.get(i).equals(allCoords.get(i - 1))) {
uniqueCoords.add(allCoords.get(i));
}
}
}
// 3. 建立映射 (也可以用二分查找代替map，在竞赛中更快)
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < uniqueCoords.size(); i++) {
map.put(uniqueCoords.get(i), i);
}
// 4. 在小索引上操作
// 创建值数组和前缀和数组
int size = uniqueCoords.size();
long[] a = new long[size];
for (AddOp op : adds) {
int index = map.get(op.x);
a[index] += op.c;
}
// 构建前缀和数组
long[] prefixSum = new long[size + 1];
for (int i = 0; i < size; i++) {
prefixSum[i + 1] = prefixSum[i] + a[i];
}
// 处理查询
for (QueryOp op : queries) {
// 注意：要找到离散化坐标轴上 >= l 的第一个位置，和 <= r 的最后一个位置
// 这里为了简化，我们假设查询的 l, r 都在 uniqueCoords 中
// 严谨的实现需要二分查找 lower_bound 和 upper_bound
Integer l_idx = map.get(op.l);
Integer r_idx = map.get(op.r);
if (l_idx == null || r_idx == null) {
// 如果查询的端点不存在于操作点中，需要更复杂的处理（通常是二分查找）
// 这里简化处理
System.out.println("Querying range " + op.l + " to " + op.r + " -> Result depends on mapping logic");
continue;
}
long result = prefixSum[r_idx + 1] - prefixSum[l_idx];
System.out.println("Sum of [" + op.l + ", " + op.r + "] is " + result);
}
}
}
重要提醒：离线 vs. 在线
前缀和、差分、离散化 都是 离线（Offline） 算法。这意味着，你必须在开始处理之前，拿到所有的操作和查询。你不能处理一个操作，马上回答一个查询，再处理下一个操作... 因为你需要预处理整个数据集（比如构建前缀和数组，或者收集所有坐标进行离散化）。
树状数组（BIT）、线段树 是 在线（Online） 算法。它们构建的结构支持实时的“单点修改”和“区间查询”。你可以在任意时刻进行一次修改，然后立刻进行一次查询并得到正确的结果，无需知道未来的操作。二维的问题，就对应二维树状数组和二维线段树。