前缀和

一维前缀和

一维前缀和主要用于计算任意区间的元素和。

计算前缀和

sum[i] =  sum[i - 1] + a[i];

计算区间[l, r]的元素和

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

二维前缀和

二维前缀和是一种用于快速计算二维数组中任意子矩阵元素之和。

// 计算矩阵的前缀和
s[x][y] = s[x - 1][y] + s[x][y - 1] - s[x - 1][y - 1] + a[x][y]
// 计算子矩阵的和
sum = s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]

主要计算公式有以上两种，计算矩阵的前缀和即计算左图中所有有颜色区域，其中s[x - 1][y]是红加绿色区域，s[x][y - 1]是黄加绿色区域；计算子矩阵的和即计算右图中蓝紫色区域。

差分

一维差分

一维差分是与一维前缀和紧密相关，它主要用于对数组进行区间更新操作，如需要对某个区间内的所有元素进行相同的增加或减少操作。
假设原数组为 \(a\), 差分数组为 \(b\)。

• 构造差分数组

\(b[1] = a[1]\)
\(b[2] = a[2] - a[1]\)
……
\(b[i] = a[i] - a[i - 1]\)
……
\(b[n] = a[n] - a[n - 1]\)

• 区间更新操作

// 对区间 [l, r] 进行加 c
b[l] =+ c;
b[r + 1] -= c;

• 数组恢复
  在对差分数组 \(b\) 进行了一系列区间更新操作后，通过计算前缀和来恢复原数组 \(a\)，即 \(a[i] = a[i − 1] + b[i]\)。

二维差分

二维差分，类似于一维差分，是一个二维数组的子矩阵进行统一的增加或减少操作。

假设原数组为 \(a\), 差分数组为 \(b\)。
对上图中的绿色区域加c。

void insert(int x1, int y1, int x2, int y2, int c)
{
    b[x1][y1] += c;
    b[x2 + 1][y1] -= c;
    b[x1][y2 + 1] -= c;
    b[x2 + 1][y2 + 1] += c;
}

insert(i, j, i, j, a[i][j]);      // 记得构建差分数组

insert(x1, y1, x2, y2, c);        // 差分数组加c

恢复原数组操作与二维前缀和类似

a[i][j] = b[i][j] + a[i − 1][j] + a[i][j − 1] − a[i − 1][j − 1]
//or 直接用b数组存储
b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1]