欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

前缀和

程序员文章站 2022-04-15 21:56:12
[toc] "前缀和" 一维前缀和 Skips 快速计算一个区间内数的和 [l,r] 定义一个数组 ,下标要从1 开始 ,边界值 定义 s[0]=0 (如果是全局变量 的 数组 不必再 初始化,若不是 记得初始化s[0]=0),记录 s[i] 为 数组 a 中第 i个数之前所有数的和 s[i] = ......

目录

一维前缀和

skips

  • 快速计算一个区间内数的和 [l,r]

  • 定义一个数组 ,下标要从1 开始 ,边界值 定义 s[0]=0 (如果是全局变量 的 数组 不必再 初始化,若不是 记得初始化s[0]=0),记录 s[i] 为 数组 a 中第 i个数之前所有数的和

  • ```s[i] = s[i-1] + a[i];// 递推公式 这里面有 i-1 所以 当 l=1 的时候 (就是从第一个数开始算的话)`下标会为 i-1 那么i-1 就得是 0 不然数就不对 ``

  • 具体计算 使用 是 s[r]-s[l-1] 因为 s[]数组记录的是 多少个数 的和 相减 正好剩下 两个下标相差的值 注意这里是 l-1 如果是 l 的话那么 剪完之后是 s[l+1] 到 s[r] 的值 中间a[l] 的

    在两个前缀里面都有,就被减掉了。

输入一个长度为n的整数序列。

接下来再输入m个询问,每个询问输入一对l, r。

对于每个询问,输出原序列中从第l个数到第r个数的和。

输入格式

第一行包含两个整数n和m。

第二行包含n个整数,表示整数数列。

接下来m行,每行包含两个整数l和r,表示一个询问的区间范围。

输出格式

共m行,每行输出一个询问的结果。

数据范围

1≤l≤r≤n1≤l≤r≤n,
1≤n,m≤1000001≤n,m≤100000,
−1000≤数列中元素的值≤1000−1000≤数列中元素的值≤1000

输入样例:

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

输出样例:

3
6
10

代码

#include<iostream>
using namespace std;
const int n=1e5+10;
int a[n],s[n];    // s[0]=0;
int n,m;
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i]; //数组 a存完之后 在 存s数组 
    for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i]; // 递推公式
    while(m--)
    {
        int l,r;
        cin>>l>>r;
        cout<<s[r]-s[l-1]<<endl; // 输出的时候下标 右端点 数值 减一 
    }
    
    
    return 0;
}

二维前缀和

skips

  • 应用:

    • 给出一个坐标,求出 以 该坐标为右下角的矩阵的元素的和
    • 给出两个坐标,求出 以 小的坐标为 左上角,大的坐标为右上角 的矩阵元素的和
  • 核心

    1. 第一个应用 : 求和 的具体操作

      // 利用了容斥原理 通过 分块的思想
      // 先读入元素
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                cin>>a[i][j];
        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]+a[i][j];
      // 加的时候 多加的 要减去  不要忘了 a[i][j]
                  
        
      
    2. 第二个应用: 做差 的具体操作

        int x1,y1,x2,y2;
        cin>>x1>>y1>>x2>>y2;
        cout<<s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]<<endl;
      // 减的时候多 减了要加回来     
          
          
          
          return 0;
      
      

输入一个n行m列的整数矩阵,再输入q个询问,每个询问包含四个整数x1, y1, x2, y2,表示一个子矩阵的左上角坐标和右下角坐标。

对于每个询问输出子矩阵中所有数的和。

输入格式

第一行包含三个整数n,m,q。

接下来n行,每行包含m个整数,表示整数矩阵。

接下来q行,每行包含四个整数x1, y1, x2, y2,表示一组询问。

输出格式

共q行,每行输出一个询问的结果。

数据范围

1≤n,m≤10001≤n,m≤1000,
1≤q≤2000001≤q≤200000,
1≤x1≤x2≤n1≤x1≤x2≤n,
1≤y1≤y2≤m1≤y1≤y2≤m,
−1000≤矩阵内元素的值≤1000−1000≤矩阵内元素的值≤1000

输入样例:

3 4 3
1 7 2 4
3 6 2 8
2 1 2 3
1 1 2 2
2 1 3 4
1 3 3 4

输出样例:

17
27
21

代码

#include<iostream>
using namespace std;
const int n=1e3+10;
int a[n][n],s[n][n];
int n,m,q;
int main()
{
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            cin>>a[i][j];
        }
    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]+a[i][j];
            
    while(q--)
    {
        int x1,y1,x2,y2;
        cin>>x1>>y1>>x2>>y2;
        cout<<s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]<<endl;
    }
        
    
    
    
    return 0;
}