前缀和专题训练

前缀和

 

前缀和、差分_小雪菜本菜的博客-CSDN博客

快速求一个静态数组某一个区间内所有数的和，( 只能查询，不能修改，不能在查询的过程中修改某个数，然后再查询 )

输入一个长度为 n 的整数序列，输入 m 个询问，问序列当中某一段数的和是多少

树状数组和线段树支持边查询边修改，时间复杂度为 O( logn )，logn 常数非常大

如果我们直接暴力做，其实是比较慢的，如果暴力做需要循环一遍，假设我们想求 L - R 这一段的总和，需要进行如下操作，时间复杂度是 O( n )

最坏情况下，l 和 r 取起点和终点，如果我们求很多次，假设求 10 w 次，每次循环 10 w 遍，总共的时间复杂度是 100 亿，会导致超时

利用前缀和可以快速计算出某一个区间内所有数的和

重新预处理一个新的数组 s 数组，si = a1 + a2 + a3 + . . . + ai，每一个 si 表示原数组的前 i 个数的和，特殊规定，s0 = 0

处理 si = si-1 + ai，循环一遍就可以得到 si，预处理 si 时间复杂度为 O( n )

得到 si 之后，怎么计算某两段之间的和？

当我们预处理 si 之后，在计算某一段的和的时候，需要计算两个数的差就可以了，只需要一次运算，可以把每一次查询的时间复杂度从 O( n ) 优化成 O( 1 )

注意 s[ 0 ] 不需要初始化，因为 s 是全局数组，如果变量定义成全局数组，初值必然是 0，如果是局部数组，初值是随机值

取边界的时候会不会有问题呢？

当 L = 1 的时候，s[ L - 1 ] = s[ 1 - 1 ] = s[ 0 ] = 0，也就是取 s[ R ]，只要前缀和下标从 1 开始，s[ 0 ] 表示 0，边界就是没问题的，否则需要特判

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
 
using namespace std;
 
const int N = 100010;
 
int n,m;
//a 表示原数组
int a[N];
//s 表示前缀和数组
int s[N];
 
int main()
{
    //读入 n 表示序列的长度,下标从 1 开始,m 表示询问个数
    scanf("%d%d", &n, &m);
    //读入 n 个数
    for(int i = 1;i <= n;i++ )
    {
        scanf("%d",&a[i]);
        s[i] = s[i - 1] + a[i]; 
    }
    //处理 m 个询问
    while(m -- ) 
    {
        //每一步读入区间的范围
        int l,r;
        scanf("%d%d", &l, &r);
        printf("%d\n",s[r] - s[l - 1]);
    }
    return 0;
}

子矩阵的和

 

上一个问题其实是在一个一维数组里面，每次希望快速求某一段一维连续区间的总和，二维前缀和思想是针对二维数组来说的

输入一个 n 行 m 列的整数矩阵，再输入 q 个询问，每个询问包含四个整数 x1、y1、x2、y2，现在求这个二维数组的某一个子矩阵里面的总和是多少

输入规模比较大，n 和 m 是1k，因此总共有 100 w 个数

假设有一个 3 × 4 的矩阵，每个格子表示数组里面的某一个数

询问 1、1、2、2        17

指的是子矩阵左上角数组下标是 ( 1，1 )，子矩阵右下角数组下标是 ( 2，2 )，假设数组下标都是从 1 开始的，求的是涂色部分子矩阵的和

询问 2、1、3、4        27

询问 1、3、3、4        21

题目给出了一个二维矩阵，每次求某一个矩阵里面的子矩阵的和是多少

如果暴力求解需要两重循环，时间复杂度比较高，有没有类似一维前缀和的解决方案呢？

答案是肯定的，首先求这个矩阵的前缀和矩阵，( 类似一维里面的前缀和数组，每一个 si 表示原数组里面前 i 个数的和 ) 前缀和矩阵每一个 Sxy 表示原矩阵当中左上角所有数的和

 

 

怎么计算前缀和矩阵，怎么通过原矩阵得到前缀和矩阵？

上面所有数的和加上左边所有数的和，左上角所有子矩阵被加了两次，要减去一次

可以利用容斥原理的思想

保证除了最后一个格子之外其他所有格子都被恰好加了一次，然后我们再把这个格子的数加上就可以了

在线性的时间复杂度之内通过原矩阵就可以计算出 Sxy，因为每个 Sxy 只用了常数次运算

假设这个格子的左上角为 ( x1，y1 ) 和 右下角 ( x2，y2 )

输入规模比较大，推荐用 scanf 读入

矩阵内元素值的绝对值在 1000 以内，整个矩阵总和的绝对值的最大值也就是 100 × 100 w 小于 10^9，不需要考虑爆 int 的问题

去掉上面所有数的和与左边所有数的和，左上角的子矩阵被去掉两次，要加上一次

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
 
using namespace std;
 
const int N = 1010;
 
int n,m,q;
//原数组 a 前缀和数组 s
int a[N][N],s[N][N];
 
int main()
{
    //n 和 m 表示原矩阵的长和宽 q 表示询问个数
    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]);
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
        }
    //处理 q 个询问 读入左上角和右下角
    while(q -- )
    {
        int x1,y1,x2,y2;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        printf("%d\n",s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]); 
    }
    return 0;
}