当前位置：首页 > news >正文

【优选算法前缀和】前缀和算法模板详解：一维前缀＆与二维前缀和

news 来源：原创 2025/7/2 9:18:29

一维前缀和

题目解析

算法原理

解法一：暴力解法

简单模拟，读完题意有 q 次询问，给哪两个数，就求哪段区间的和并且返回，这样的做法，时间复杂度为O(N*q)，这个时间复杂度会超时；

解法二：前缀和

前缀和算法的应用场景，就是快速求出数组中某一个连续区间的和；

暴力解法需要从头到尾遍历一次数组，时间复杂度为O(N)，而前缀和可以在连续区间以一个O(1)的时间复杂度求和；所以有q次求和，总的时间复杂度为O(q)；

(1) 预处理出一个前缀和数组

预处理出来的前缀和数组，我们命名为 dp ；

并且与原始数组 arr 相同大小，比如 arr 的下标是从1到9，那么 dp 的下标也是从 1 到 9：

dp 的每一个元素 dp[i]，表示 [ 1 , i ] 区间内所有元素的和：

小技巧：dp[ i +1] = dp[ i ] + arr [ i ]

(2) 使用前缀和数组

有了前缀和数组，如果要求 [ l , r ] 区间的和，只需要求 dp[ r ] - dp [ l -1 ] 即可；

而使用前缀和数组来对一段连续区间进行求和，时间复杂度为 O(1)，如果有 q 次求和，总的时间复杂度为 O(N) + O(q)；

我们可以把同一类问题，抽象成一个状态表示；

(3) 处理细节问题

为什么下标要从 1 开始计数呢？如果从 0 开始计数，当有一次要查询 [ 0 , 2 ] 区间的和：

带入这条公式，就变成了 dp[2] - dp[ -1]，数组无法访问 -1 位置的元素，所以出现这种情况需要特殊处理；

而数组从 1 下标位置开始计数，查询 [ 1 , 3] 区间的和，就变成了 dp[3] - dp[ 0 ] ，我们只需要把 dp [0] 置为 0即可，避免处理边界情况；

在动态规划中，把 dp[0]置为0，就是添加辅助节点的步骤，添加辅助节点来帮助初始化，能够避免处理一些边界情况；

编写代码

二维前缀和

题目解析

算法原理

解法一：暴力解法

通过给出的坐标，直接求出子矩阵所有元素之和即可；时间复杂度，每次询问，最差情况是都得求出子矩阵中每个元素之和，就得遍历整个矩阵一遍，时间复杂度为O(n*m*q)；

解法二：前缀和

(1) 预处理出一个前缀和矩阵

重新创建一个同等规模的矩阵 dp，dp[i][j] 表示从 [1,1] 到 [ i , j ] 里所有元素之和；

我们需要快速找出规律，来求出 dp[i][j] 的值是多少，否则每求一个元素，就要遍历一次用来的矩阵，那么创建 dp 表的时间复杂度也会很大；

我们可以根据所求的 dp[i][j]，将原来的 A 矩阵分成四个部分，最终要求的 dp[i][j] 等于 A+B+C+D，可以类比面积的求和过程；dp[ i-1][ j-1 ]=A，但是 B C 区域不好求：

我们可以转换思路，求AB，AC再减去重复计算的部分，即可求出 B，C区域；并且，我们总结出了求 dp[i][j] 的公式：

通过公式，就可以用公式以O(1) 的时间复杂度，来预处理前缀和矩阵；

(2) 使用前缀和矩阵

创建好前缀和矩阵后，该怎么使用呢？我们通过分割：

转换成公式如下：

当得到递推公式，每次拿到 [x1 , y1] ~ [ x2 , y2 ]，直接套用这条公式，就可以以 O(1) 的时间复杂度来求和两个坐标围成的子矩阵；

对比暴力解法，使用前缀和矩阵的时间复杂度为，在预处理前缀和数组的时间复杂度为 O(m*n)，再查询 q 次求和结果，时间复杂度 O(q)；得到的总时间复杂度 O( m*n + q )；

编写代码

【优选算法前缀和】前缀和算法模板详解：一维前缀＆与二维前缀和

一维前缀和题目解析算法原理解法一：暴力解法简单模拟，读完题意有 q 次询问，给哪两个数，就求哪段区间的和并且返回，这样的做法，时间复杂度为O(N*q)，这个时间复杂度会超时&#xf…...

编程日记 2025/7/2 9:18:29

【记录】用JUnit 4的@Test注解时报错java.lang.NullPointerException的原因与解决方法

项目场景： 在练习黑马点评的逻辑过期解决缓存击穿时，编写了一个预热缓存数据的单元测试 SpringBootTest public class HmDianPingApplicationTests {Resourceprivate ShopServiceImpl shopService;Testpublic void testSaveShop() throws InterruptedE…...

编程日记 2025/7/2 10:28:08

Transformer入门（6）Transformer编码器的前馈网络、加法和归一化模块

文章目录 7.前馈网络8.加法和归一化组件9.组合所有编码器组件构成完整编码器 7.前馈网络编码器块中的前馈网络子层如下图所示： 图1.32 – 编码器块前馈网络由两个带有ReLU激活函数的全连接层组成。全连接层（Fully Connected Layer）有时也…...

编程日记 2025/6/28 19:01:32

（七）腾讯cloudstudio+Stable-Diffusion-webui AI绘画教程-安装Stable-Diffusion-WebUI

一、说明本文选择安装stable-diffusion-webui最新版本 cloud studio 免费版最大的问题是空间不足，我晚上上传时超过了硬盘大小，直接不能启动，没办法，删除，又建了一个工作空间二、安装 1、打开终端 2、配置Git代理…...

编程日记 2025/7/2 21:04:51

算法基础Day7(动态规划)

文章目录 1.题目2.题目解答1.第N个泰波那契数题目及题目解析动态规划算法学习1.状态表示2.状态转移方程3.初始化4.填表顺序5.空间优化代码提交空间优化 2.三步问题题目及题目解析算法学习代码提交 1.题目 1137. 第 N 个泰波那契数 - 力扣（LeetCode）面试…...

编程日记 2025/7/1 7:19:45

代理IP地址和端口是什么？怎么进行设置？

保护个人隐私、突破地域限制、提升网络安全性是我们不断追求的目标。IP地址与端口一种实现这些目标的重要工具。但是，你可能对它是什么，以及如何设置感到困惑。别担心，本文将为你揭开这些神秘的面纱，让你轻松掌握这项技能。 1.IP…...

编程日记 2025/7/1 21:29:45

一文详解TCP协议 [图文并茂, 明了易懂]

欢迎来到啊妮莫的学习小屋! 目录什么是TCP协议 TCP协议特点✨ TCP报文格式三次握手和四次挥手✨ 可靠性效率性基于字节流✨ 基于TCP的应用层协议什么是TCP协议 TCP(传输控制协议, Transmission Control Protocol) 是一种面向连接的, 可靠的, 基于字节流的传输层通…...

编程日记 2025/7/2 19:50:35

js后端开发之Next.js、Nuxt.js 与 Express.js

后端js之Next.js、Nuxt.js 与 Express.js 在现代 Web 开发中，JavaScript 已经成为前后端通用的编程语言，而选择合适的后端框架则是构建高效、可扩展应用程序的关键。本文将带你深入了解三个流行的 JavaScript 后端框架：Next.js、Nuxt.js 和 …...

编程日记 2025/7/1 23:28:50

人工智能概要

目录前言1.什么是人工智能（Artificial Intelligence, AI）2.人工智能发展的三次浪潮2.1 人工智能发展的第一次浪潮2.2 人工智能发展的第二次浪潮2.3 人工智能发展的第三次浪潮 3.人工智能发展的必备三要素3.1 数据3.2 算法（algorithm&#xf…...

编程日记 2025/7/2 21:14:18

spring boot 3集成swagger

Spring Boot 3 集成 Swagger 的过程与之前版本相比有一些变化，主要是因为 springfox 库已经停止更新，并且不再支持新的 Spring Boot 版本。因此，对于 Spring Boot 3 来说，推荐使用 springdoc-openapi 作为集成 Swagger 的解决方案…...

编程日记 2025/7/2 9:18:53

【PlantUML系列】状态图（六）

一、状态图的组成部分状态：对象在其生命周期内可能处于的条件或情形，使用 state "State Name" as Statename 表示。初始状态：表示对象生命周期的开始，使用 [*] 表示。最终状态：表示对象生命周期的结束&…...

编程日记 2025/7/2 20:38:23

前端缓存页面处理方法

当前一个前端应用新发布时，重新编译后，原来引用的资源文件名都会有变化。如果这个应用的页面在前端浏览器中有缓存，则会导致加载资源失败。怎样去除这种缓存，同时也能尽可能的保证前端访问的性能 ChatGPT said: ChatGPT 这是一个经…...

编程日记 2025/7/1 23:07:22

284. 窥视迭代器想要提前知道下一个内容，就需要缓存 class PeekingIterator : public Iterator { public:PeekingIterator(const vector<int>& nums) : Iterator(nums) {// Initialize any member here.// **DO NOT** save a copy of nums and manipula…...

编程日记 2025/7/2 9:56:35

Cesium-（Primitive）-（BoxGeometry）

含实现代码 GISer世界效果: 以下是 BoxGeometry 类的构造函数属性，以表格形式展示：属性名类型默认值描述minimumCartesian3盒子的最小 x, y, 和 z 坐标。maximumCartesian3盒子的最大 x, y, 和 z 坐标。vertexFormatVertexFormatVertexFormat.DEFAULT要计算的顶点属性。以下…...

编程日记 2025/7/1 19:24:21

CSS元素宽高特点、类型转化、显式和隐藏（display）

元素的宽高特点块级元素可以设置宽高，不可以和其他元素在一行设置宽高时，元素的宽高为设置的值没有设置宽高时，宽度和父级宽高一样，高度由元素内容决定行级元素不可以设置宽高，可以和其他元素在一行元素的宽高…...

编程日记 2025/7/2 21:11:17

上市公司投资效率Biddle模型数据（包括最终数据、原始数据及构造说明）2003-2022年

一、计算方式：参考《Journal of accounting and economics》Biddle G C，构建Biddle模型使用企业投资对成长机会的回归模型来估计企业的投资效率，这里成长机会用销售增长率来衡量。回归模型如下图所示: 二、资料范围：包括原始数据…...

编程日记 2025/7/2 4:12:37

矩阵的乘(包括乘方)和除

矩阵的乘分为两种： 一种是高等代数中对矩阵的乘的定义：可以去这里看看包含矩阵的乘。总的来说，若矩阵 A s ∗ n A_{s*n} As∗n列数和矩阵 B n ∗ t B_{n*t} Bn∗t的行数相等，则 A A A和 B B B可相乘，得到一个矩阵 …...

编程日记 2025/7/2 1:39:48

Spring Security6.3 自定义AuthorizationManager问题

项目环境： Springboot3.3.5, 对应的SpringFrameWork6.1，Security为6.3 问题：我想自定义AuthorizationManager接口实现类，在里面判断如果角色为amdin则放行请求； 在AdminAuthorizationManager类的check()方法中pass变量…...

编程日记 2025/6/28 18:10:17

第一部分：基础知识 9 . 视图 --[MySQL轻松入门教程]

在MySQL中，视图（View）是一个命名的SQL查询，它被存储在数据库目录中。视图可以包含来自一个或多个表的数据，并且可以像真实表一样被查询。下面是对MySQL视图的详细讲解：创建视图使用 CREATE VIEW 语句来创建视图。语法如下： CREATE [OR REPLACE] [ALGORITHM = {UNDEFIN…...

编程日记 2025/6/28 20:15:00

用GPT零负担学单片机之点亮一颗cpu 第3节训练or特征匹配？用GPT开发嵌入式

用GPT零负担学单片机之点亮一颗cpu 第3节训练or特征匹配？AI写代码大家好,我是小杰学长如果你是大学生遇到电子技术学习成长入行难题我曾经通过大学比赛赚钱从事嵌入式AI 航天军工用特别的学习和求职方法线下半年带50+学弟学妹入行开发主页佳喔威信，给你提供一定资…...

编程日记 2025/7/2 20:46:05

2.6、vue2中侦听属性的变化

2.6.1、侦听属性作用侦听属性的变化其实就是监视某个属性的变化。当被监视的属性一旦发生改变时，执行某段代码。2.6.2、watch配置项监视属性变化时需要使用watch配置项可以监视多个属性，监视哪个属性，请把这个属性的名字拿过来即可。 i.可以监视Vue的原有属性 ii.如果监视的…...

编程日记 2025/6/28 18:53:28

enable_shared_from_this

用途 struct S {shared_ptr<S> dangerous(){return shared_ptr<S>(this); // dont do this!} };int main() {shared_ptr<S> sp1(new S);shared_ptr<S> sp2 sp1->dangerous();return 0; }考虑以上代码，从一个被shared_ptr管理的struc…...

编程日记 2025/6/28 18:44:41

重生之我在异世界学智力题（2）

大家好，这里是小编的博客频道小编的博客：就爱学编程很高兴在CSDN这个大家庭与大家相识，希望能在这里与大家共同进步，共同收获更好的自己！！！ 本文目录引言智力题：逃离孤岛智力题&a…...

编程日记 2025/7/2 19:35:53

深入解析下oracle的number底层存储格式

oracle数据库中，number数据类型用来存储数值数据，它既可以存储负数数值，也可以存储正数数值。相对于其他类型数据，number格式的数据底层存储格式要复杂得多。今天我们就详细探究下oracle的number底层存储格式。一、环境搭建 1.…...

编程日记 2025/7/2 8:20:52

prometheus

1.安装，tar包，解压即用 tar xf prometheus-2.33.3.linux-amd64.tar.gz -C /app/tools/ 2.创建软链接 ln -s prometheus-2.33.3.linux-amd64/ /app/tools/prometheus 3.进入目录 cd /app/tools/prometheus 4.运行 ./prometheus 5.此时&#xff0…...

编程日记 2025/7/1 1:26:36

C# 23种设计模式（1）单例模式（单件模式）

一、单例模式介绍单例模式（Singleton Pattern）是一种创建型设计模式，它确保一个类只有一个实例，并提供一个全局访问点。这个模式在需要一个对象被共享且全局唯一的情况下非常有用，比如配置对象、日志对象、数据库连接…...

编程日记 2025/7/2 9:28:02

Javaweb：HTML、CSS

学习资源1 学习资源 2 黑马javaweb HTML 1、基础标签、样式图片标签：<img> src:绝对路径、相对路径(绝对磁盘路径，网络路径；./当前目录）width:宽度（百分比）height:高度（百分比&…...

编程日记 2025/7/1 10:34:33

SmartDV将SDIO系列IP授权给RANiX开发车联网（V2X）产品

双方的合作将增强符合ISO 26262标准的车联网（V2X）系统的通信和连接能力，加速实现更安全、更智能的汽车系统和车辆创新加利福尼亚州圣何塞市，2024年12月——灵活、高度可配置、可定制化的半导体设计知识产权（IP&#…...

编程日记 2025/6/28 18:49:33

【Android】创建型设计模式—单例模式、工厂模式、建造者模式

单例模式单例模式（Singleton Pattern）是一种创建型设计模式，它确保一个类只有一个实例，并提供全局访问点。单例模式类图： #mermaid-svg-kzf6IdXdYeNOHtP0 {font-family:"trebuchet ms",verdana,arial,sa…...

编程日记 2025/6/28 18:11:41

ida9pro压缩包

资源类型的博客大部分都是为了自己某天换新机了用下载链接2：ida9.zip 下载链接1：https://mega.nz/folder/yiAiVDAa#T0kogEE7ufqy0x0EpCuOLQ 主目录下该文件为证书文件 ida9中选择它，就可以了...

编程日记 2025/7/2 9:25:59

前端入门之VUE--vue组件化编程

前言 VUE是前端用的最多的框架；这篇文章是本人大一上学习前端的笔记；欢迎点赞收藏关注，本人将会持续更新。文章目录 2、Vue组件化编程2.1、组件2.2、基本使用2.2.1、VueComponent 2、Vue组件化编程 2.1、组件组件：用来实现…...

编程日记 2025/7/2 16:15:49

C++是如何工作的？

首先来看一个最基本的C程序段。 #include <iostream>int main() {std::cout << "HelloWorld" << std::endl;std::cin.get(); } 第一行 #include 的含义是预处理的意思，这条语句的作用是将一个名为iostream的文件拷贝到源代码中这个…...

编程日记 2025/6/28 18:12:00

JavaScript中的this, 究竟指向什么？

在JavaScript代码的不同位置中，this所指向的数据是不一样的。比如大部分同学都知道，在对象的函数属性方法中，this指向对象本身；在构造函数中，this指向要生成的新对象。事实上，this指向的逻辑不止这几种&…...

编程日记 2025/7/2 1:23:46

JavaWeb学习(3)（Servlet详细、Servlet的三种实现方式(面试)、Servlet的生命周期、传统web.xml配置Servlet(了解)）

目录一、Servlet详细。 （1）基本介绍。 （2）基本作用。 1、接收客户端请求数据。 2、处理请求。 3、完成响应结果。二、Servlet的三种实现方式。 （1）实现javax.servlet.Servlet接口。 1、基本介绍。 2、代码…...

编程日记 2025/7/2 4:54:06

【图像去雾数据集】URHI数据集介绍

URHI数据集对应论文：RESIDE: A Benchmark for Single Image Dehazing（2017） URHI数据集下载链接：https://sites.google.com/site/boyilics/website-builder/reside 为便于下载，将上述官方提供的链接中百度云链接粘贴如…...

编程日记 2025/6/28 19:41:52

Playwright中Page类的方法

导航和页面操作 goto(url: str, **kwargs: Any): 导航到一个URL。 reload(**kwargs: Any): 重新加载当前页面。 go_back(**kwargs: Any): 导航到会话历史记录中的前一个页面。 go_forward(**kwargs: Any): 导航到会话历史记录中的下一个页面。 set_default_navigation_tim…...

编程日记 2025/6/29 13:11:53

算力介绍与解析

算力（Computing Power）是指计算机系统在单位时间内处理数据和执行计算任务的能力。算力是衡量计算机性能的重要指标，直接影响计算任务的速度和效率。算力的分类和单位 a. 基础算力：以CPU的计算能力为主。适用于各个领域的计算。…...

编程日记 2025/6/28 18:57:28

CentOS 上如何查看 SSH 服务使用的端口号？

我们知道，linux操作系统中的SSH默认情况下，端口是使用22，但是有些线上服务器并不是使用的默认端口，那么这个时候，我们应该如何快速知道SSH使用的哪个端口呢？ 1、通过配置文件查看 cat /etc/ssh/sshd_confi…...

编程日记 2025/6/28 18:08:14

每日算法Day03

1.19.删除链表的倒数第N个节点算法链接: 19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode） 类型: 链表难度: 中等思路：采用双指针法，控制两个指针之间的距离为n个节点易错点：返回节点的确定和头节点的处理&…...

编程日记 2025/6/28 5:35:44

【漏洞复现】Apache Solr 身份认证绕过导致任意文件读取漏洞复现（CVE-2024-45216）

🏘️个人主页：点燃银河尽头的篝火(●’◡’●) 如果文章有帮到你的话记得点赞👍+收藏💗支持一下哦【漏洞复现】Apache Solr 身份认证绕过导致任意文件读取漏洞复现（CVE-2024-45216）一、漏洞概述1.1漏洞简介1.2组件描述1.3漏洞描述二、漏洞复现2.1 应用协议2.2 环境…...

编程日记 2025/6/28 19:31:29

若依将数据库更改为SQLite

文章目录 1. 添加依赖项2. 更新配置文件 application-druid.yml2.1. 配置数据源2.2. 配置连接验证 3. 更新 MybatisPlusConfig4. 解决 mapper 中使用 sysdate() 的问题4.1. 修改 BaseEntity4.2. 修改 Mapper 5. 更新 YML 配置正文开始： 前提条件：在您的…...

编程日记 2025/7/1 20:21:59

ubuntu远程桌面开启opengl渲染权限

背景最近用windows的【远程桌面连接】登录ubuntu后（xrdp协议），发现gl环境是集显的，但是本地登录ubuntu桌面后是独显（英伟达），想要在远程桌面上也用独显渲染环境。一、查看是独显还是集显环境…...

编程日记 2025/6/30 20:15:02

Scala的泛型

需求:定义一个名为getMiddleEle 的方法用它来获取当前的列表的中间位置的值中间位置的下标长度/2目标:getMiddleEle(List(1,2,3,4,5)) > 5/2 2 > 下标为2的元素是:3 getMiddleEle(List(1,2,3,4)) > 4/2 2 > 下标为2的元素是:3格式如下: 定义一个函数的格式:def…...

编程日记 2025/7/2 11:37:48

每隔一秒单片机向电脑发送一个16进制递增数据

SCON0x50 SM00 SM11（工作方式为方式一） REN1允许单片机从电脑接收数据 TB8 RB8 SM2是方式2和方式3直接配置为0 TI为发送中断请求标志位由硬件配置为1 必须由软件复位为0，RI为接收中断请求标志位，同理TI UART.c #include &l…...

编程日记 2025/6/30 18:31:42

轻量级日志管理平台：Grafana Loki搭建及应用（详细篇）

前言 Grafana Loki是Grafana Lab团队提供的一个水平可扩展、高可用性、多租户的日志聚合系统，与其他日志系统不同的是，Loki最初设计的理念是为了为日志建立标签索引，而非将原日志内容进行索引。现在目前成熟的方案基本上都是：L…...

编程日记 2025/6/28 9:30:45

React和Vue.js的相似性和差异性是什么？

React和Vue.js都是现代前端开发中广泛使用的JavaScript框架，它们都旨在提高开发效率和组件化开发。以下是他们的一些相似性和差异性： 相似性组件化：两者都支持组件化开发，允许开发者将UI拆分成独立的、可复用的组件。虚拟DOM&a…...

编程日记 2025/6/30 1:41:31

跨域 Cookie 共享

跨域请求经常遇到需要携带 cookie 的场景，为了确保跨域请求能够携带用户的认证信息或其他状态，浏览器提供了 withCredentials 这个属性。如何在 Axios 中使用 withCredentials 为了在跨域请求中携带 cookie，需要在 Axios 配置中设置 withCr…...

编程日记 2025/7/1 4:43:22

全国青少年信息学奥林匹克竞赛（信奥赛）备考实战之计数器与累加器（一）

学习背景： 在现实生活中一些需要计数的场景下我们会用到计数器，如空姐手里记录乘客的计数器，跳绳手柄上的计数器等。累加器是累加器求和，以得到最后的结果。计数器和累加器它们虽然是基础知识，但是应用广泛&#xff0…...

编程日记 2025/7/2 1:39:48

红黑树（Red-Black Tree）

一、概念红黑树（Red Black Tree）是一种自平衡的二叉搜索树，通过添加颜色信息来确保在进行插入和删除操作时，树的高度保持在对数级别，从而保证了查找、插入和删除操作的时间复杂度为 O(log n)。这种树可以很好地解决普…...

编程日记 2025/7/1 7:34:23

火电厂可视化助力提升运维效率

图扑智慧火电厂综合管理平台实现对火电厂关键设备和系统的实时监控和数据分析。图扑可视化不仅优化了运维流程，还增强了安全管理，有效提升了电厂整体运营效率。...

编程日记 2025/6/28 18:08:18

一维前缀和

二维前缀和

相关文章：