开发者社区> 辰Chen> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

前缀和算法

简介: 复习acwing算法基础课的内容,本篇为讲解基础算法:前缀和,关于时间复杂度:目前博主不太会计算,先鸽了,日后一定补上.
+关注继续查看

文章目录

前言

一、关于前缀和

二、一维数组求前缀和

1.求段区间前缀和

2.例题:AcWing795. 前缀和

AC代码

三、二维数组求前缀和

1.求S[i,j]

2.求(x1,y1),(x2,y2)子矩阵的和

3.例题:AcWing796. 子矩阵的和

AC代码

四、时间复杂度分析

前言

复习acwing算法基础课的内容,本篇为讲解基础算法:前缀和,关于时间复杂度:目前博主不太会计算,先鸽了,日后一定补上.


什么是前缀和:例如一个数组:a[1],a[2],a[3]…a[n],前缀和S[i]表示的是该数组的前i项的和,例如S[3] = a[1] + a[2] + a[3],S[i] = a[1] + a[2] + a[3] + … + a[i - 1] + a[i].

一、关于前缀和

注:前缀和要求下标从1开始,可以避免下标的转换,对于a[0]的处理:赋值为0即可,从而S[1] = a[0] + a[1] = 0 + a[1] = a[1];S[2] = a[0] + a[1] + a[2] = 0 + a[1] + a[2] = a[1] + a[2]。对于S[N],a[N]数组可以定义为全局变量,这样a[0]初始值就为0


前缀和的作用:快速求出某段区间内元素的和


二、一维数组求前缀和

1.求段区间前缀和

for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);       //读入n个数

for (int i = 1; i <= n; i ++ ) s[i] = s[i - 1] + a[i];   //处理前缀和

2.例题:AcWing795. 前缀和

本题链接:AcWing795. 前缀和

本博客给出题目截图:

image.png

AC代码

#include <cstdio>

using namespace std;

const int N = 100010;

int a[N], s[N];

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    
    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
    
    for (int i = 1; i <= n; 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;
}

三、二维数组求前缀和

1.求S[i,j]

如图,用i表示行,j表示列:

image.png

根据图分析:求s[i, j]:

s[i, j] = s[i, j - 1] + s[i - 1, j] - s[i - 1, j - 1] + a[i, j];

2.求(x1,y1),(x2,y2)子矩阵的和

如图:

image.png

根据图分析:求s[x1 ~ x2, y1 ~ y2]:

s[x1 ~ x2, y1 ~ y2] = s[x2,y2] - s[x2, y1-  1] - s[x1 - 1, y2] + s[x1 - 1,y1 - 1];

3.例题:AcWing796. 子矩阵的和

本题链接:AcWing796. 子矩阵的和

本博客给出题目截图:

image.png

image.png

AC代码

#include <cstdio>

using namespace std;

const int N = 1010;

int a[N][N], s[N][N];

int main()
{
    int 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]);                      //读入矩阵
            
    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]; //计算每个s[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[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]);//计算子矩阵
    }
    
    return 0;
}

四、时间复杂度分析

关于前缀和的时间复杂度以及证明,后续会给出详细的说明以及证明过程,目前先鸽了。

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
前缀和算法模板
前缀和算法模板
10 0
【算法】贪心算法
【算法】贪心算法
41 0
算法总结
猫狗队列 注意: 查找了一些网上的写法,发现很多样本再处理pollAll pollDog pollCat方法的时候,并不是如下边的要求弹出所有,原因不详,以我对文字的 敏感性来说,这种只弹出一个的方式是错误的,奈何很多公司的算法题 答案也是如此,所以暂且先这样处理,你完全可以添加一个循环将所有 元.
1210 0
推荐算法
![_](http://img2.tbcdn.cn/L1/461/1/3dfea01b820ffdbefae79c239ec67b43e1c8d555.png) 相关阅读: - [Spark机器学习3·推荐引擎](http://www.
1710 0
递归算法
/*编写一个递归函数完成以下公式的运算*/ //sum(n)=1-1/2+1/3-1/4......(其中n>0) #include using namespace std; //非递归算法 float FUN(int n) { int m=1,temp=1; float total=0.
549 0
+关注
辰Chen
CSDN人工智能领域优质创作者,华为云&middot;云享专家,CCF-TYUT President-designate
719
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载