刷题笔记-前缀和

前缀和是快速求取静态数组内某一区间内所有数的和的一种方法。如果在求取的过程中数组发生变动，则可以采用树状数组、线段树等方法。

例题1 一维前缀和

输入一个长度为n的整数序列。
接下来再输入m个询问，每个询问输入一对l, r。
对于每个询问，输出原序列中从第l个数到第r个数的和。
输入格式
第一行包含两个整数n和m。
第二行包含n个整数，表示整数数列。
接下来m行，每行包含两个整数l和r，表示一个询问的区间范围。
输出格式
共m行，每行输出一个询问的结果。

数据范围

\(1≤l≤r≤n\)
\(1≤n,m≤100000\)
\(?1000≤数列中元素的值≤1000\)

#include <cstring>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int n,m;
int s[N];
int a[N];
int main(void)
{
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;i++)
    {
        scanf("%d",&a[i]);
        s[i] = s[i-1] + a[i];
    } 
    while(m--)
    {
        int l,r;
        scanf("%d%d",&l,&r);
        printf("%d\n",s[r] - s[l-1]);
    }
    return 0;
    
}

例题2 二维前缀和

输入一个n行m列的整数矩阵，再输入q个询问，每个询问包含四个整数x1, y1, x2, y2，表示一个子矩阵的左上角坐标和右下角坐标。
对于每个询问输出子矩阵中所有数的和。
输入格式
第一行包含三个整数n，m，q。
接下来n行，每行包含m个整数，表示整数矩阵。
接下来q行，每行包含四个整数x1, y1, x2, y2，表示一组询问。
输出格式
共q行，每行输出一个询问的结果。
数据范围
\(1≤n,m≤1000\)
\(1≤q≤200000\)
\(1≤x1≤x2≤n\)
\(?1000≤矩阵内元素的值≤1000\)

#include <cstring>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1010;
int a[N][N];
int s[N][N];
int n,m,q;
int main(void)
{
    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];
        }
    while(q--)
    {
        int x1,x2,y1,y2;
        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]);
    }
    return 0;
    
            

}

练习1 K倍区间

给定一个长度为N的数列，如果其中一段连续的子序列之和是K的倍数，我们就称这个区间[i,j]是K倍区间。
你能求出数列中总共有多少个K倍区间吗？

数据范围

\(1≤N,K≤100000\)
\(1≤Ai≤100000\)

思路：

1. 通过二重循环控制子序列的起始和终止位置，遍历求每个每个子序列的和 S[r] - S[l-1] % k 是否等于0，时间复杂度是\(O(n^2)\),大约\(10^9\)量级，所以需要考虑降低时间复杂度。
   2.降低时间复杂度的一般方式是用空间换时间.
2. S[r] - S[l-1] % k == 0 等价于 s[r] % k == s[l-1] % k,所以可以声明一个数组用来保存余数为 s[i] % k 的个数,这样只需要一层循环即可.
   4.注意数据溢出的情况

代码：

#include <cstring>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 100010;
int n,k;
LL s[N],cnt[N];
int main(void)
{
    scanf("%d %d",&n,&k);
    //计算前缀和
    for(int i = 1; i <= n;i++){
        scanf("%lld",&s[i]);     //注意LL的读取
        s[i] += s[i-1];
    }
    LL ans = 0;                 //注意答案可能溢出
    for(int i = 0;i <= n;i++)   //考虑和为0也也是k倍区间,所以从0开始遍历
    {
        //假设已经有两个S[i]的余数为x,则又有一个S[i]%k == x时，会产生两个新的答案，所以有下面两句
        ans += cnt[s[i] % k];
        cnt[s[i] % k]++;
    }
    printf("%lld",ans);
    return 0;
}

刷题笔记-前缀和

原文：https://www.cnblogs.com/zy200128/p/12616856.html