前缀和与差分

1.AcWing795.一维前缀和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int n, m;
int arr[MAX], prefix[MAX];

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; ++i) scanf("%d", &arr[i]);
    for (int i = 1; i <= n; ++i) prefix[i] = prefix[i - 1] + arr[i];//前缀和数组初始化
    while (m--) {
        int low, high;
        scanf("%d %d", &low, &high);
        printf("%d\n", prefix[high] - prefix[low - 1]);
    }
    return 0;
}

2.AcWing796.二维前缀和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int n, m, q;
int arr[MAX][MAX], prefix[MAX][MAX];
nt main() {
    scanf("%d %d %d", &n, &m, &q);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            scanf("%d", &arr[i][j]);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            prefix[i][j] = prefix[i - 1][j] + prefix[i][j - 1] - prefix[i - 1][j - 1] + arr[i][j];//前缀初始化
    while (q--) {
        int x1, y1, x2, y2;
        scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
        printf("%d\n", prefix[x2][y2] + prefix[x1 - 1][y1 - 1] - prefix[x1 - 1][y2] - prefix[x2][y1 - 1]);
    }
    return 0;
}

3.AcWing797.一维差分

差分的作用：可以用O(1)的时间来实现对原数组，中间的某一段区间数值全部加上一个固定的值C，只需要在差分数组中修改两数即可。

给区间[l, r]中的每个数加上c：B[low] += c; B[high + 1] -= c;

image-20230321095547796

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int n, m;
int a[MAX];
int b[MAX];//差分数组

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

int main() {
    //1.构造差分数组b[]
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    for (int i = 1; i <= n; ++i) insert(i, i, a[i]);//根据已知的数组a[] 构造差分数组b[]
    //2.对差分数组 b[] 进行 +c 运算
    while (m--) {
        int low, high, c;
        scanf("%d %d %d", &low, &high, &c);
        insert(low, high, c);
    }
    //3.将差分数组b[] 还原为 前缀和数组 并输出最终结果
    for (int i = 1; i <= n; ++i) b[i] += b[i - 1];
    for (int i = 1; i <= n; ++i) printf("%d ", b[i]);
    return 0;
}

4.AcWing798.二维差分

给以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵中的所有元素加上C：

  • S[x1, y1] += c,
  • S[x2 + 1, y1] -= c,
  • S[x1, y2 + 1] -= c,
  • S[x2 + 1, y2 + 1] += c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
int n, m, q;
int a[MAX][MAX];
int b[MAX][MAX];//差分数组

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;
}

int main() {
    //1.构造差分数组b[]
    scanf("%d %d %d", &n, &m, &q);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            scanf("%d", &a[i][j]);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            insert(i, j, i, j, a[i][j]);
    //2.对差分数组 b[] 进行 +c 运算
    while (q--) {
        int x1, y1, x2, y2, c;
        scanf("%d %d %d %d %d", &x1, &y1, &x2, &y2, &c);
        insert(x1, y1, x2, y2, c);
    }
    //3.将差分数组b[] 还原为 前缀和数组 并输出最终结果
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) printf("%d ", b[i][j]);
        printf("\n");
    }
    return 0;
}