前缀和

2020-05-04 16:00:20来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

前缀和

目录

  • 前缀和
  • 一维前缀和
    • Skips
    • 模板题
    • 代码
  • 二维前缀和
    • Skips
    • 模板题
    • 代码

前缀和

一维前缀和

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


原文链接:https://www.cnblogs.com/xuexijiaoliu/p/12826549.html
如有疑问请与原作者联系

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:博弈--尼姆博弈

下一篇:单调队列模板【附例题】