一维差分与二维差分

差分（Difference）是一种与前缀和密切相关的技术，主要用于高效处理区间更新操作。差分数组的核心思想是通过记录相邻元素的差值来表示原数组的变化，从而将区间更新操作的时间复杂度从 O(n) 优化到 O(1)。下面详细讲解一维差分和二维差分的原理、构建方法及应用。

---

一、一维差分

1. 定义

• 差分数组 diff 的每个元素 diff[i] 表示原数组 arr 中相邻元素的差值，即：
  [
  \text{diff}[i] = \text{arr}[i] - \text{arr}[i-1]
  ]
• 例如，原数组 arr = [1, 3, 6, 10]，差分数组为 diff = [1, 2, 3, 4]。

2. 构建方法

• 初始化 diff[0] = arr[0]。
• 递推公式：
  [
  \text{diff}[i] = \text{arr}[i] - \text{arr}[i-1]
  ]
• 代码实现：

  vector<int> buildDiff(vector<int>& arr) {int n = arr.size();vector<int> diff(n, 0);diff[0] = arr[0];for (int i = 1; i < n; i++) {diff[i] = arr[i] - arr[i - 1];}return diff;
  }
  

3. 区间更新

• 对原数组 arr 的区间 [L, R] 进行更新（增加一个值 val）：
  [
  \text{diff}[L] += \text{val}, \quad \text{diff}[R+1] -= \text{val}
  ]
• 示例：
  arr = [1, 3, 6, 10]，对区间 [1, 2] 增加 2：
  [
  \text{diff}[1] += 2, \quad \text{diff}[3] -= 2
  ]
  更新后的差分数组为 diff = [1, 5, 3, 2]。

4. 还原原数组

• 通过差分数组 diff 还原原数组 arr：
  [
  \text{arr}[i] = \text{arr}[i-1] + \text{diff}[i]
  ]
• 代码实现：

  vector<int> restoreArray(vector<int>& diff) {int n = diff.size();vector<int> arr(n, 0);arr[0] = diff[0];for (int i = 1; i < n; i++) {arr[i] = arr[i - 1] + diff[i];}return arr;
  }
  

5. 应用场景

• 高效处理区间更新操作（如区间加、区间减）。
• 解决需要频繁更新和查询的问题（如航班预订统计）。

---

二、二维差分

1. 定义

• 二维差分数组 diff 的每个元素 diff[i][j] 表示原矩阵 matrix 中相邻元素的差值。
• 例如，矩阵 matrix = [[1,2],[3,4]]，差分数组为：
  [
  \text{diff} = \begin{bmatrix}
  1 & 1 \
  2 & 0 \
  \end{bmatrix}
  ]

2. 构建方法

• 初始化 diff[0][0] = matrix[0][0]。
• 递推公式：
  [
  \text{diff}[i][j] = \text{matrix}[i][j] - \text{matrix}[i-1][j] - \text{matrix}[i][j-1] + \text{matrix}[i-1][j-1]
  ]
• 代码实现：

  vector<vector<int>> build2DDiff(vector<vector<int>>& matrix) {int m = matrix.size();int n = matrix[0].size();vector<vector<int>> diff(m, vector<int>(n, 0));diff[0][0] = matrix[0][0];for (int i = 1; i < m; i++) {diff[i][0] = matrix[i][0] - matrix[i - 1][0];}for (int j = 1; j < n; j++) {diff[0][j] = matrix[0][j] - matrix[0][j - 1];}for (int i = 1; i < m; i++) {for (int j = 1; j < n; j++) {diff[i][j] = matrix[i][j] - matrix[i - 1][j] - matrix[i][j - 1] + matrix[i - 1][j - 1];}}return diff;
  }
  

3. 区间更新

• 对原矩阵 matrix 的子矩阵 (x1, y1) 到 (x2, y2) 进行更新（增加一个值 val）：
  [
  \text{diff}[x1][y1] += \text{val}, \quad \text{diff}[x2+1][y1] -= \text{val}, \quad \text{diff}[x1][y2+1] -= \text{val}, \quad \text{diff}[x2+1][y2+1] += \text{val}
  ]
• 示例：
  matrix = [[1,2],[3,4]]，对子矩阵 (0,0) 到 (1,1) 增加 2：
  [
  \text{diff}[0][0] += 2, \quad \text{diff}[2][0] -= 2, \quad \text{diff}[0][2] -= 2, \quad \text{diff}[2][2] += 2
  ]
  更新后的差分数组为 diff = [[3,1],[2,0]]。

4. 还原原矩阵

• 通过差分数组 diff 还原原矩阵 matrix：
  [
  \text{matrix}[i][j] = \text{matrix}[i-1][j] + \text{matrix}[i][j-1] - \text{matrix}[i-1][j-1] + \text{diff}[i][j]
  ]
• 代码实现：

  vector<vector<int>> restoreMatrix(vector<vector<int>>& diff) {int m = diff.size();int n = diff[0].size();vector<vector<int>> matrix(m, vector<int>(n, 0));matrix[0][0] = diff[0][0];for (int i = 1; i < m; i++) {matrix[i][0] = matrix[i - 1][0] + diff[i][0];}for (int j = 1; j < n; j++) {matrix[0][j] = matrix[0][j - 1] + diff[0][j];}for (int i = 1; i < m; i++) {for (int j = 1; j < n; j++) {matrix[i][j] = matrix[i - 1][j] + matrix[i][j - 1] - matrix[i - 1][j - 1] + diff[i][j];}}return matrix;
  }
  

5. 应用场景

• 高效处理子矩阵更新操作（如子矩阵加、子矩阵减）。
• 图像处理中的区域像素更新。

---

三、对比总结

特性	一维差分	二维差分
数据结构	一维数组	二维数组
构建复杂度	O(n)	O(mn)
更新复杂度	O(1)	O(1)
核心公式	diff[i] = arr[i] - arr[i-1]	diff[i][j] = ...（见上文）
应用问题	区间更新、航班预订统计	子矩阵更新、图像处理

---

四、经典例题

1. 一维差分：

   • LeetCode 1109. 航班预订统计
   • LeetCode 370. 区间加法

2. 二维差分：

   • LeetCode 2536. 子矩阵元素加 1