3.10前缀和与差分

3.10前缀和与差分
- 一维前缀和：一维数组区间求和
- 二维前缀和：二维矩阵区间求和
- 一维差分：一维数组区间修改
- 二维差分：二维矩阵区间修改
- 洛谷练习题目

一维前缀和：一维数组区间求和

给定长度为 $n$ 的序列 $a[1],a[2]...a[n]$, 则 $sum[i] = a[1]+...+a[i] = sum[i-1]+a[i]$.

【题目描述】
给定长度为 $n(n<=1e5)$ 的序列 $a[1],a[2],...,a[n]$,
给定 $q (q<=1e5)$ 个询问 $[l,r]$，输出 $[l,r]$ 的区间和。

【输入格式】
第一行输入 $n, q$ ;
第二行输入序列 $a[1],a[2],...,a[n]$；
接下来 $q$ 行，每行两个数据，分别对应 $l, r$。

【输出格式】
输出 $q$ 行，表示 $[l, r]$ 区间和。

【输入样例】

10  5
1 2 3 4 5 5 4 3 2 1
1 6
3 8
1 10
5 5
1 3

【输出样例】

方法1：暴力计算每个询问 $[l,r]$，时间复杂度： $O(q ×n)$

方法2：前缀和，输出每个询问 $[l,r]$，时间复杂度： $O(n + q)$

#include
using namespace std;

const int N=1e5+10;
int a[N], sum[N];

int main(){
    freopen("data.in", "r", stdin);
    int n,m,l,r; scanf("%d%d", &n, &m);
    for(int i=1; i<=n; i++) scanf("%d", &a[i]);
    for(int i=1; i<=n; i++){ //前缀和预处理
        sum[i] = sum[i-1]+a[i];
    }
//    printf("  下标："); for(int i=1; i<=n; i++) printf("%3d", i); printf("\n");
//    printf("原数组："); for(int i=1; i<=n; i++) printf("%3d", a[i]); printf("\n");
//    printf("前缀和："); for(int i=1; i<=n; i++) printf("%3d", sum[i]);printf("\n\n");

    for(int i=1; i<=m; i++){
        scanf("%d%d", &l, &r);
        printf("l=%2d r=%2d sum[L~R]=%d\n", l, r, sum[r]-sum[l-1]);
    }
    return 0;
}

二维前缀和：二维矩阵区间求和

给定一个矩阵 $s[i][j]$，$sum[i][j]$是矩阵 $s[1...i][1...j]$ 的和。

使用二维前缀和可以在 $O(1)$ 时间内求一个矩阵和。

【题目描述】
给定一个 $n*m (n,m<=1e4)$ 大小的矩阵 $a$，
有 $q (q<=1e4)$ 次询问，每次询问给定 $x1,y1,x2,y2$ 四个数，
求以 $(x1,y1)$ 为左上角坐标和 $(x2,y2)$ 为右下角坐标的子矩阵的所有元素和。
注意仍然包含左上角和右下角的元素。

【输入格式】
第一行输入 $n, m, q$ ;
接下来 $n$ 行, 每行 $m$ 个数据，表示矩阵元素；
接下来 $q $ 行，每行 $4$ 个数据，分别对应 $x1,y1,x2,y2$。

【输出格式】
输出 $q$ 行，表示以 $(x1,y1)$ 为左上角坐标和 $(x2,y2)$ 为右下角坐标的子矩阵的所有元素和。

【输入样例】

【输出样例】

#include
using namespace std;

const int N=1e4+10;
int a[N][N], sum[N][N];
int n,m,q,x1,y1,x2,y2,ans=0;
void print();

int main(){
    freopen("data.in", "r", stdin);
    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]);  // 二维前缀和预处理
            sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];
        }
    }
//    print();// 打印输出

    for(int i=1; i<=q; i++){
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        ans = sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1];
        printf("%d\n", ans);
//        printf("(%d,%d)->(%d,%d): ans=%d\n", x1, y1, x2, y2, ans);
    }
    return 0;
}

void print(){
    printf("原数组：\n");
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++) printf("%3d", a[i][j]);
        printf("\n");
    }printf("\n");

    printf("二维前缀和数组：\n");
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++) printf("%3d", sum[i][j]);
        printf("\n");
    }printf("\n");
}

一维差分：一维数组区间修改

差分：每个元素与前一个元素的差值
如原数组 arr: 1 2 3 4 5
则差分为 dif: 1 1 1 1 1  ( dif[] 的前缀和即为 arr[])

单点修改 arr[i]+add:
若将 arr[1]+1, 则 arr: 1 3 3 4 5
       则差分数组 dif: 1 2 0 1 1,
只会改变自己和后一个数, 即 dif[i] += add,  dif[i+1] -= add.

区间修改 [l,r] 增加 add:
若将 arr 数组 [2,4] 每个元素+1, arr: 1 3 4 5 5
                    则差分数组 dif: 1 2 1 1 0,
只会改变 dif[l] 和 dif[r] 后一个数,即 dif[l] += add, dif[r+1] -= add.

【题目描述】
给定长度为 $n(n<=1e5)$ 的序列 $a[1],a[2],...,a[n]$,初始都为 0，
接着 $m(m<=1e5)$ 个操作 $l,r,add$ ，表示给 $a$ 数组 $[l,r]$ 区间内的每个数加 $add$，
给定 $q(q<=1e5)$ 个询问输出 $a[i]$ 的值。

输入样例：

10 5 10
1 2 1
2 2 2
2 2 3
5 8 4
2 10 5
1 2 3 4 5 6 7 8 9 10

输出样例：

1 10 -6  0  4  0  0  0 -4  0

#include
using namespace std;

const int N=1e5+10;
int a[N], sum[N], dif[N];
int n,m,q,l,r,add,id;
void print();

int main(){
    freopen("data.in", "r", stdin);
    scanf("%d%d%d", &n, &m, &q);
    for(int i=1; i<=m; i++){
        scanf("%d%d%d", &l, &r, &add);
        dif[l] += add;
        dif[r+1] -= add;
    }
    for(int i=1; i<=n; i++){
        sum[i] =sum[i-1]+dif[i];
    }
    print();// 打印输出

    for(int i=1; i<=q; i++){
        scanf("%d", &id);
        printf("%3d", sum[id]-sum[id-1]);
    }
    return 0;
}

void print(){
    printf(" 下标:\n");
    for(int i=1; i<=n; i++) printf("%3d", i); printf("\n");

    printf("差分数组:\n");
    for(int i=1; i<=n; i++) printf("%3d", dif[i]); printf("\n");

    printf("前缀和数组:\n");
    for(int i=1; i<=n; i++) printf("%3d", sum[i]); printf("\n");

    printf("原数据数组:\n");
    for(int i=1; i<=n; i++) printf("%3d", sum[i]-sum[i-1]); printf("\n");
}

二维差分：二维矩阵区间修改

有一个二维矩阵

1 2 4 3
5 1 2 4
6 3 5 9

对应的二维差分矩阵如下：

1  1  2 -1
4 -5 -1  3
1  1  1  2

【题目描述】
输入一个 $n$ 行 $n$ 列的整数矩阵，再输入 $q$ 个操作，
每个操作包含五个整数 $x1，y1，x2，y2，c$，
其中 $(x1, y1)$ 和 $(x2, y2)$ 表示一个子矩阵的左上角坐标和右下角坐标。
每个操作都要将选中的子矩阵中的每个元素的值加上 $c$。
请你将进行完所有操作后的矩阵输出。

输入格式：
第一行包含整数 $n，m，q$。
接下来 $n$ 行，每行包含 $m$ 个整数，表示整数矩阵。
接下来 $q$ 行，每行包含 $5$ 个整数 $x1，y1，x2，y2，c$，表示一个操作。

输出格式：
共 $n$ 行，每行 $m$ 个整数，表示所有操作进行完毕后的最终矩阵。

输入样例：

输出样例：

2 3 4 1
4 3 4 1
2 2 2 2

数据范围：

\[1 ≤ n, m ≤ 1000, \quad 1 ≤ q ≤ 100000,\\ 1 ≤ x1 ≤ x2 ≤ n, \quad 1 ≤ y1 ≤ y2 ≤ m,\\ 1000 ≤ c ≤ 1000, \quad 1000 ≤ 矩阵内元素的值 ≤ 1000 \]

#include
using namespace std;

const int N=1e4+10;
int a[N][N], sum[N][N], dif[N][N];
int n,m,q,x1,y1,x2,y2,c;

int main(){
    freopen("data.in", "r", stdin);
    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]);
            dif[i][j]=a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1];
        }
    }
    for(int i=1; i<=q; i++){
        scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &c);
        dif[x1][y1] += c;
        dif[x1][y2+1] -= c;
        dif[x2+1][y1] -= c;
        dif[x2+1][y2+1] += c;
    }

    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            dif[i][j] += dif[i-1][j]+dif[i][j-1]-dif[i-1][j-1];
            printf("%3d", dif[i][j]);
        }printf("\n");
    }
    return 0;
}

洛谷练习题目

P5638 【CSGRound2】光骓者的荣耀
P1115 最大子段和
P3397 地毯
P1719 最大加权矩形
P3406 海底高铁
P2004 领地选择

信息学普及组3

3.10前缀和与差分