1. 全栈程序员必看首页

前缀和算法

全栈程序员-站长 • • 未分类 • 阅读 1

前缀和算法文章目录前言一 关于前缀和二 一维数组求前缀和 1 求段区间前缀和 2 例题 AcWing795 前缀和 AC 代码三 二维数组求前缀和 1 求 S i j 2 求 x1 y1 x2 y2 子矩阵的和 3 例题 AcWing796 子矩阵的和 AC 代码四 时间复杂度分析前言关于时间复杂度 目前博主不太会计算 先鸽了 日后一定补上 什么是前缀和 例如一个数组 a 1 a 2 a 3 a n 前缀和 S i 表示的是该数组的前 i 项的和 例如 S 3 a 1 a 2 a 3 S i

文章目录

前言

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

一、关于前缀和

注：前缀和要求下标从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. 前缀和

AC代码

#include  
       using namespace std; const int N = ; 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]

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

2.求（x1，y1），（x2，y2）子矩阵的和

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

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

AC代码

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

四、时间复杂度分析

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

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。

发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/207819.html原文链接：https://javaforall.net

赞 (0)
0 0

关于作者

全栈程序员-站长的头像

全栈程序员-站长

133.5K 文章
3 粉丝
本网站汇聚当前互联网主流语音，持续更新，欢迎关注公众号“全栈程序员社区”
上一篇 2026年3月19日 下午1:01
下一篇 2026年3月19日 下午1:02


相关推荐

  • springboot框架的理解_谈谈你对springmvc的理解

    springboot框架的理解_谈谈你对springmvc的理解

    springboot框架的理解_谈谈你对springmvc的理解1.起源SpringBoot是由Pivotal团队提供的全新框架，其设计目的是用来简化新Spring应用的初始搭建以及开发过程。该框架使用了特定的方式来进行配置，从而使开发人员不再需要定义样板化的配置。用我的话来理解，就是SpringBoot其实不是什么新的框架，它默认配置了很多框架的使用方式，就像Maven整合了所有的Jar包，SpringBoot整合了所有的框…

    全栈程序员-站长的头像 全栈程序员-站长
    2022年8月20日
    7
  • 顺序OleDbCommand命名参数，你了解不？

    顺序OleDbCommand命名参数，你了解不？

    顺序OleDbCommand命名参数，你了解不？   接触到一个老的项目，里面大量使用OleDbConnection进行数据库操作，在执行SQL块语句时，对它的顺序参数、命名参数很不了解。据说不能使用命名参数，但我这里试验了一下，好像是可以的，只是对参数的顺序还是有要求。看看你能知道下面的输出结果吗？   测试环境：OleDbConnection+Oracle10G   using System;using System.Data…

    全栈程序员-站长的头像 全栈程序员-站长
    2022年5月19日
    39
  • 从零实现反思Agent 全栈程序员

    从零实现反思Agent

    从零实现反思Agent

    全栈程序员-站长的头像 全栈程序员-站长
    2026年3月16日
    2
  • document.getElementById的理解

    document.getElementById的理解

    document.getElementById的理解个人现在的理解就是在一个页面中找到对应id的模块

    全栈程序员-站长的头像 全栈程序员-站长
    2022年7月15日
    24
  • MySQL之权限管理

    MySQL之权限管理

    MySQL之权限管理MySQL之权限管理

    全栈程序员-站长的头像 全栈程序员-站长
    2022年4月24日
    52
  • Java中Random用法

    Java中Random用法

    Java中Random用法今天看帖子时候看到了蓄水池算法，想起来之前看到过这样的题目，记录一下用到的Random类吧，面试写算法应该会碰到这样的题目。首先Random是随机生成数用法，介绍一下：1、Random.nextInt()：这个用法就是生成一个Int范围里的一个随机数，用法举个例子：Randonmrandom=newRandom;System.out.println(random.nextInt());这时候输出的就是一个随机数，范围就是int的范围，当然括号里是可以填参数的，比如random.nextInt

    全栈程序员-站长的头像 全栈程序员-站长
    2022年7月7日
    23

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

关注全栈程序员社区公众号