Casey

前缀和与差分

最近更新：2025-03-05 | 字数总计：1.1k | 阅读估时：4分钟 | 阅读量：次

前缀和与差分互为逆操作，其都是人为构造的、用于简化算法的方法，以下从构造方法和作用两个方面来看这两个操作。

前缀和

一维前缀和

对于一个一维矩阵，其前缀和定义为。在代码中，为了便于计算，通常将数组 a[] 从序号 1 开始存储，并令 a[0] = 0，前缀和数组的构造方式如下。

vector<int> s(a.size(), 0);
for (int i = 1; i < s.size(); i++) {
  s[i] = s[i - 1] + a[i];
}

一维前缀和的作用在于快速求出数组 a[] 在某一区间 [i,j] 的和，其为 s[j] - s[i - 1]。

二维前缀和

二维前缀和的定义方式类似于一维前缀和，但其构造与作用的对象为二维矩阵，定义为。
在代码中，同样一般将数组 a[][] 从序号 1 开始存储，并令 a[i][0] = a[j][0] = 0。不同于一维数组可以直接使用 s[i - 1] 计算 s[i]，二维数组中 s[i][j] 的递推计算需要使用到容斥原理，如下。

vector<vector<int>> s(a.size(), vector<int>(a[0].size(), 0));
for (int i = 1; i < a.size(); i++) {
  for (int j = 1; j < a[0].size(); j++) {
    s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
  }
}

二维前缀和的作用在于快速求出二维矩阵在某一矩形区间中的元素和，也需要使用到容斥原理。例如，求数组 a[][] 在区间 [x1, y1] 至 [x2, y2]（x1 < x2, y1 < y2）中元素和，为 s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1]。

差分

不同于前缀和可以直接的理解到其实际意义，差分的构造需要严格从定义来理解，特别是二维差分。

一维差分

对于一个一维矩阵，其差分定义为。在代码中，数组 a[] 应从序号 1 开始存储，并且令 a[0] = 0，一维差分数组的代码构造如下。

vector<int> d(a.size(), 0);
for (int i = 1; i < a.size(); i++) {
  d[i] = a[i] - a[i - 1];
}

从前缀和的构造过程可以发现一个特点，一个 a[i] 的改变会使 s[j]（j >= i）发生改变。由于差分是前缀和的逆操作，那么差分操作的作用在于对某一区间中的元素进行快速加减操作，并且这种改变只需要改变差分数组中的两个元素。例如，我们需要对 a[] 中区间 [i,j] 上的元素均加上一个值 c，那么我们只需要作如下操作。

void insert(vector<int> &d, int i, int j, int c) {
  d[i] += c;
  if (j + 1 < d.size()) { // 边界处理
    d[j + 1] -= c;
  }
}

有了差分数组 d[] 后，我们可以通过一次遍历求前缀和从中快速的恢复出改变后的数组 a[]。

另外，基于 insert() 函数，不难发现，除了从定义构造差分数组外，还可以使用 insert() 函数间接构造差分数组。

vector<int> d(a.size(), 0);
for (int i = 1; i < a.size(); i++) {
  insert(d, i, i, a[i]);
}

二维差分

对于二维矩阵，其差分定义为。类似于一维差分，数组 a[][] 应从序号 1 开始存储，从定义角度其构造方式如下。

vector<vector<int>> d(a.size(), vector<int>(a[0].size(), 0));
for (int i = 1; i < a.size(); i++) {
  for (int j = 1; j < a[0].size(); j++) {
    d[i][j] = a[i][j] - a[i - 1][j] - a[i][j - 1] + a[i - 1][j - 1];
  }
}

二维差分的作用在于对二维区间中的元素进行快速加减操作。例如，我们需要对 a[][] 中区间 [x1, y1] 至 [x2, y2]（x1 < x2, y1 < y2）上的元素均加上一个值 c，可以类比一维差分构造二维差分，代码如下。

void insert(vector<vector<int>> &d, int x1, int y1, int x2, int y2, int c) {
  d[x1][y1] += c;
  if (x2 + 1 < d.size() && y2 + 1 < d[0].size()) {
    d[x2 + 1][y2 + 1] += c;
  }
  if (x2 + 1 < d.size()) {
    d[x2 + 1][y1] -= c;
  }
  if (y2 + 1 < d[0].size()) {
    d[x1][y2 + 1] -= c;
  }
}

类比于一维差分，我们同样可以使用 insert() 函数间接构造二维差分，如下。

vector<vector<int>> d(a.size(), vector<int>(a[0].size(), 0));
for (int i = 1; i < a.size(); i++) {
  for (int j = 1; j < a[0].size(); j++) {
    insert(d, i, j, i, j, a[i]);
  }
}

2025-03-05 该篇文章被 Casey 打上标签: 算法 C++ 归为分类: 学习