Road Map

打怪路线：

• 一维前缀和：303 -> 525

• 二维前缀和：303 -> 304 -> 1314

• 一维差分：

• 子数组的性质：523 -> 525

前缀和

一维前缀和

对于一个给定的数列 $A$ ，它的前缀和数列 $S$ 是能通过递推求出的基本信息之一。

$S[i] = \sum_{j=1}^i A[j]$

数列 $A$ 的区间和 $[L, R]$

$sum(l, r) = \sum_{j=L}^R A[i] = S[R] - S[L-1]$

795. 前缀和 (opens new window)

for (int i = 0; i < n; i++){
  cin >> A[i];
  S[i + 1] = S[i] + A[i];
}
while (m--){
  cin >> l >> r;
  cout << S[r] - S[l-1] << endl;
}

二维前缀和

容斥原理的应用

二维前缀和

给定二维数组 int[m][n] grid

定义二维前缀和int[m+1][n+1] s

初始化：

// grid 下标从 0 开始
s = new int[m+1][n+1];
for (int i = 1; i<=m; i++){
  for (int j = 1; j<=n; j++){
    s[i][j] = grid[i-1][j-1] + s[i-1][j] + s[i][j-1] - s[i-1][j-1];
  }
}

子矩阵和：

// 左上角（x1,y1）右下角(x2,y2)
// 注意:点的坐标都是从0开始的
S{(x1,y1),(x2,y2)} = s[x2+1][y2+1] - s[x1][y2+1] - s[x2+1][y1] + s[x1][y1];

796. 子矩阵的和 (opens new window)

for (int i = 1; i <= n; i++){
  for (int j = 1; j <= m; j++ ){
    scanf("%d", &s[i][j]);
    s[i][j] += s[i-1][j] + s[i][j-1] - s[i-1][j-1];
  }
}
while (q--)
{
  scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
  printf("%d\n", s[x2][y2] - s[x2][y1 -1] - s[x1 -1][y2] + s[x1-1][y1-1] ) ;
}

99. 激光炸弹 (opens new window)

差分

“前缀和” 和 “差分” 是一对互逆运算：

• 前缀和序列 的 差分序列 为 原序列
• 差分序列的前缀和序列为原序列 差分实现 的核心思路 是 实现 $insert$ 操作；

一维差分

对于一个给定的数列 $A$，它的差分数列 $B$ 定义为：

$B[1] = A[1], B[i] = A[i] - A[i-1] (2<=i<=n)$

容易发现，“前缀和” 和 “差分” 是一对互逆运算。

差分序列 $B$ 的前缀和序列就是 原序列 $A$；

前缀和序列的 差分序列 也是 原序列 $A$ ；

把 序列 $A$ 的区间 $[l, r]$ 加 $d$，其差分序列 $B$ 的变化为 $B_l$ 加 $d$ ，$B_{r+1}$ 减 $d$。这样把原序列 $A$ 上的 “区间操作” 转化为 差分数列 $B$ 上的单点操作。

$insert()$ 实现

在 $[l, r]$ 区间内 增加 $C$ ， 可以在 左端点 记录 增加 $C$ ，在右端点的下一个端点 减去 $C$

void insert(int l, int r, int c){
    b[l] += c; b[r+1] -= c;
}

我们可以把单个元素 $A[i]$ 的插入 看做是 区间 $[i, i]$ 整体加上 $A[i]$，于是就可以使用 原序列进行 $insert$ 操作直接得到 差分序列

一维数组的返回

使用一维前缀和 计算

AcWing 797. 差分 (opens new window)

const int N = 100010;
int n, m;
int l, r, c;
int a[N]; // 求原数组 = 差分数组的前缀和 （可省略）
int b[N]; // 差分数组
void insert(int l, int r, int c){
    b[l] += c; b[r+1] -= c;
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) {
        int c;
        scanf("%d", &c);
        insert(i, i, c);
    }
    while (m -- ){
        scanf("%d%d%d", &l, &r, &c);
        insert(l, r, c);
    }
    for (int i = 1; i <= n; i ++ ) {
        b[i] += b[i-1];
        printf("%d ", b[i]);
    }
}

AcWing 100. 增减序列 (opens new window)

二维差分（差分矩阵）

定义 差分矩阵 $S_{1<=i,j<=n} [i][j]$ ；

差分矩阵 和 前缀和矩阵互为逆运算：即 差分矩阵 的 前缀和矩阵 为原矩阵，前缀和矩阵的 差分矩阵为原矩阵；

$insert()$实现

同一维差分， $insert$ 方法的实现 也是 差分矩阵的核心。

$insert(x1,y1,x2,y2,C)$ 操作定义：给 $(x1,y1),(x2,y2)$ 组成的矩阵中的每一个元素增加 $C$。

• 记录 $S[x1, y1]$ 增加 $C$ ，表示 所有在 $(x1,y1)$ 右下方的元素 增加 $C$；

• 记录 $S[x2 + 1, y1]$ 减去 $C$ ，表示 所有在 $(x2,y2)$ 正下方的元素 减去 $C$；

• 记录 $S[x1, y2 + 1]$ 减去 $C$ ，表示 所有在 $(x2,y2)$ 正右方的元素 减去 $C$；

• 我们发现 这时 $(x2,y2)$ 右下方的元素被减去了两次，所以需要增加一步操作：$S[x2+1, y2+1]$ 增加 $C$ 。

矩阵的返回

使用 二维前缀和 返回原矩阵

798. 差分矩阵

const int N = 1010;
int n,m,q;
int x1,y1, x2,y2,c;
int s[N][N];

int insert(int x1, int y1, int x2, int y2, int C){
    s[x1][y1] += C;
    s[x2+1][y1] -=C;
    s[x1][y2+1] -= C;
    s[x2+1][y2+1] += C;
}
int main()
{
    scanf("%d%d%d", &n, &m, &q);

    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ ) {
            int c;
            scanf("%d", &c);
            insert(i, j, i, j, c);
        }
    while (q -- ){
        scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &c);
        insert(x1, y1, x2, y2, c);
    }
    for (int i = 1; i <= n; i ++ ){
        for (int j = 1; j <= m; j ++ ){
            s[i][j] += s[i-1][j] + s[i][j-1] - s[i-1][j-1];
            printf("%d ",s[i][j]);
        }
        cout << endl;
    }

    return 0;
}