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

算法题（129）：二维前缀和

news 来源：原创 2025/8/3 6:50:53

审题：

本题需要我们将q组矩阵的和打印出来

思路：
方法一：二维前缀和

由于本题使用暴力的模拟方法运行次数高达1e11，会超时，所以我们采用运行次数在1e6的二维前缀和来解题

第一步：前缀和的求法

x = i，y = j的二维矩阵前缀和f[i][j]就是A + B + C + a[i][j]

而为了将式子转化为表达式，我们可以将式子和前缀和联系起来：
(A+B) + （A+C）- A + a[i][j]

而A+B的面积就是x=i-1，y=j的位置的前缀和：f[i-1][j]

其他同理，于是转化为：f[i][j] = f[i-1][j]+f[i][j-1]-f[i-1][j-1]+a[i][j]

第二步：根据矩阵的左上角坐标和右下角坐标确定矩阵和

思考方法和前面类似：

f[x2][y2] = A+B+C+answer

=> (A+B)+(A+C)-A+answer

最终推导得到：answer = f[x2][y2]+f[x1-1][y1-1]-f[x1-1][y2]-f[x2][y1-1]

解题：

#include<iostream>
using namespace std;
typedef long long ll; 
ll n,m,q;
const ll N = 1e3+10;
ll f[N][N];//前缀和数组
ll a[N][N];
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++){f[i][j] = f[i-1][j] + f[i][j-1] - f[i-1][j-1] + a[i][j];}}//数据处理并输出while(q--){ll x1,x2,y1,y2;cin >> x1 >> y1 >> x2 >> y2;ll answer = f[x2][y2]+f[x1-1][y1-1]-f[x1-1][y2]-f[x2][y1-1];cout << answer << endl;}return 0;
}

注意：

1.本题采取索引为1的存储方式：

其一是为了和题目给的索引对应

其二是为了避免进行边界检查，因为推导的公式中存在访问i-1或j-1的，如果从索引为0开始计算会出现越界访问-1的情况

2.本题需要采用long long 类型：因为题目中的数据范围是-1e9~1e9，这是很大的，如果进行运算很容易就超过int的存储范围

【模板】二维前缀和

相关文章：

算法题（129）：二维前缀和

审题&#xff1a; 本题需要我们将q组矩阵的和打印出来 思路&#xff1a; 方法一&#xff1a;二维前缀和 由于本题使用暴力的模拟方法运行次数高达1e11&#xff0c;会超时&#xff0c;所以我们采用运行次数在1e6的二维前缀和来解题 第一步&#xff1a;前缀和的求法 x i&#xf…...

编程日记 2025/8/3 6:50:53

NEAT 算法解决 Lunar Lander 问题：从理论到实践

NEAT 算法解决 Lunar Lander 问题：从理论到实践 0. 前言1. 定义环境2. 配置 NEAT3. 解决 Lunar lander 问题小结系列链接0. 前言 在使用 NEAT 解决强化学习问题一节所用的方法只适用于较简单的强化学习 (reinforcement learning, RL) 环境。在更复杂的环境中使用同样的进化解…...

编程日记 2025/8/2 17:19:57

Arduino示例代码讲解：Project 07 - Keyboard 键盘

Arduino示例代码讲解：Project 07 - Keyboard 键盘 Project 07 - Keyboard 键盘程序功能概述功能：硬件要求：输出：代码结构全局变量`setup()` 函数`loop()` 函数读取电位器值：打印电位器值：播放音调：运行过程注意事项Project 07 - Keyboard 键盘 /*Arduino Starter Kit e…...

编程日记 2025/8/3 6:42:09

4.凸包-Graham Scan

Graham Scan:Algorithm Preprocessing 根据角度进行排序 Graham Scan 例子 例2 Graham Scan:Correctness Left Turn/right Trun 下一个点出现的两种情况&#xff1a;非蓝即绿 Presorting 预排序很重要&#xff1a;否则所有的点都会满足 to-left-test BackTracks算法复杂度 …...

编程日记 2025/8/3 6:40:55

系统架构师2025年论文《论SOA技术的应用》

摘要&#xff1a; 本人于XXXX年XX月参加某市医院《预约挂号系统》的开发工作&#xff0c;在该项目中主要担任系统架构师&#xff0c;主要负责该系统架构和网络安全体系架构设计。经过多年的医院信息化建设&#xff0c;某市医院已经建立了一些应用系统&#xff0c;但是&#xf…...

编程日记 2025/8/3 6:48:01

React+TS编写轮播图

当前轮播图存在部分问题&#xff0c;一次循环结束&#xff0c;进入下一次需要点击两次&#xff08;所以动画效果上点击第二次才出现&#xff09; 轮播图&#xff1a;实现无限循环轮播图的关键在于"视觉欺骗"——我们在实际数据的前后各添加部分数据副本&#xff0c;当…...

编程日记 2025/8/3 6:45:55

山东大学创新项目实训开发日志（19）之前端知识深度学习

今天晚上在队长的带领下学习了一下前端vue的基础知识 reactive和ref函数 refreactive数据类型原始数据、对象对象操作js中需要添加.value&#xff0c;tamplate中则不用都不用添加.value computed和watch computed 写法 <script setup>const Factorial computed(() &g…...

编程日记 2025/8/3 6:37:21

【C++详解】C++入门(一)

文章目录 一、命名空间命名空间的基本特性命名空间的使用 二、C输入输出用法三、缺省参数(默认参数)定义用法 四、函数重载 一、命名空间 命名空间的基本特性 #include <stdio.h> #include <stdlib.h>int rand 10;int main() {// 编译报错&#xff1a;error C23…...

编程日记 2025/8/3 6:36:57

MAC-从es中抽取数据存入表中怎么实现

使用 Java 从 Elasticsearch 抽取数据并存入数据库表的完整实现方案： 1. Maven 依赖配置 <dependencies><!-- Elasticsearch --><dependency><groupId>org.elasticsearch.client</groupId><artifactId>elasticsearch-rest-high-level-c…...

编程日记 2025/8/3 6:36:58

Android串口通信

最近因为需要在Android平台进行电子秤的开发&#xff0c;首先第一步就是需要解决Android串口通信获取电子秤的称重信息。 google官方给我们提供了现成的解决方案&#xff0c;里面有编译好的apk文件还有源代码可以直接参考使用。地址&#xff1a;http://code.google.com/p/andr…...

编程日记 2025/8/3 6:42:12

QT常见输入类控件及其属性

Line Edit QLineEdit用来表示单行输入框&#xff0c;可以输入一段文本&#xff0c;但是不能换行 核心属性&#xff1a; 核心信号 信号 说明 void cursorPositionChanged(int old,int new) 当鼠标移动时发出此型号&#xff0c;old为先前位置&#xff0c;new为新位置 void …...

编程日记 2025/8/3 6:44:41

RAG 与 MCP 如何以不同方式解决大模型的局限性

Claude 和 GPT-4o 等大型语言模型 (LLM) 功能强大&#xff0c;但也面临两个主要限制&#xff1a;它们包含的知识是时效性的&#xff08;更具体地说&#xff0c;是在训练时点固定的&#xff09;&#xff0c;并且决定它们一次可以处理多少信息的上下文窗口是有限的。 检索增强生…...

编程日记 2025/8/3 6:36:32

[Windows]_[VS2017]_[如何进行远程调试程序]

场景 在开发Windows程序时&#xff0c;有时候在测试机上测试出异常操作的情况&#xff0c;在开发机上就是出现不了。还比如在测试机上能测试到崩溃的情况&#xff0c;在开发机上也是重现不了&#xff0c;怎么办&#xff1f; 说明 这种情况可能是测试机上的系统版本&#xff0…...

编程日记 2025/8/3 6:42:10

Retinex系列图像/视频增强算法介绍

Retinex 系列原理基础 一、核心原理与理论 Retinex算法基于人类视觉系统特性，认为观测到的图像由光照分量(L)与反射分量( R )乘积构成，即： S ( x , y ) = L ( x , y...

编程日记 2025/8/3 6:43:40

游戏引擎学习第237天:使用 OpenGL 显示图像

win32_game.cpp: 禁用 PFD_DOUBLEBUFFER 我们正在处理一个新的开发阶段&#xff0c;目标是在使用 OpenGL 渲染的同时能正常通过 OBS 进行直播。昨天我们已经尝试了一整天来解决这个问题&#xff0c;希望能找到一种方式让 OBS 能正确地捕捉到 OpenGL 的窗口画面。虽然我们不确定…...

编程日记 2025/8/3 6:50:48

【C++基本算法】背包问题——完全背包

7. 背包问题——完全背包 文章目录 7. 背包问题——完全背包【模板】完全背包零钱兑换零钱兑换∥完全平方数问题解决注意事项 【模板】完全背包 题目链接&#xff1a; 【模板】完全背包 要点&#xff1a; 完全背包核心逻辑&#xff1a;物品无限次选择&#xff0c;状态转移方…...

编程日记 2025/8/3 6:50:03

Spring 01

今天是2025/0420 19:44 day 21 总路线请移步主页Java大纲相关文章 今天进行Spring 1,2,3 个模块的归纳 最近在忙毕设&#xff0c;更新有点慢&#xff0c;见谅 首先是Spring 的相关内容概括的思维导图 一、核心概念详解 1. IoC容器 1.1 工作原理 // 典型使用示例 Applica…...

编程日记 2025/8/2 17:17:27

小迪第10天http/s数据包

HTTP数据包 浏览器请求&请求头&响应头 浏览器访问流程 请求:用户–>web服务器 (Request) 响应:web服务器–> 用户(Response) 加代理后 请求:用户–>代理–>web服务器 (Request) 响应:web服务器–>代理–> 用户(Response) http GET请求头 http post…...

编程日记 2025/8/3 6:42:43

网络设备基础运维全攻略：华为/思科核心操作与巡检指南

一、设备登录与基础操作体系 1. 安全登录策略与环境准备 &#xff08;1&#xff09;登录方式深度解析 协议华为/H3C命令思科命令安全性应用场景Telnettelnet 192.168.1.1telnet 192.168.1.1明文传输本地测试&#xff08;禁止公网使用&#xff09;SSHssh -l admin 192.168.1.…...

编程日记 2025/8/2 13:56:33

Jsp技术入门指南【八】利用EL表达式开发无脚本的JSP页面

Jsp技术入门指南【八】利用EL表达式开发无脚本的JSP页面 前言一、什么是EL&#xff1f;二、EL如何访问作用域&#xff1f;2.1 对比传统脚本 vs EL2.2 EL的“自动搜索机制” 三、EL运算规则&#xff1a;什么能相加&#xff1f;什么不能&#xff1f;四、EL如何访问集合和数组&…...

编程日记 2025/8/3 6:39:12

MySQL数据库（基础篇）

一&#xff1a;MySQL的概述 1&#xff1a;MySQL数据库的下载地址 MySQL &#xff1a;&#xff1a; 下载 MySQL 安装程序 2&#xff1a;MySQL的客户端连接方式 1&#xff1a;使用Mysql自带的来连接 2&#xff1a;使用windows自带的命令行来来连接&#xff08;需要配置path环…...

编程日记 2025/8/3 6:36:30

OpenCV 图像调整指南

OpenCV 提供了多种图像调整功能&#xff0c;以下是常见的视觉图片调整方法&#xff1a; 一、基本调整 1. 调整亮度和对比度 import cv2 import numpy as npdef adjust_brightness_contrast(img, brightness0, contrast0):# 亮度和对比度调整# brightness: -100 到 100 (0 表示…...

编程日记 2025/7/28 23:34:16

云效部署实现Java项目自动化部署图解

前言 记录下使用云效部署Java项目&#xff0c;实现java项目一键化自动化部署。 云效流程说明&#xff1a; 1.云效拉取最新git代码后 2.进行maven编译打包后&#xff0c;上传到指定服务器目录 3.通过shell脚本&#xff0c;先kill java项目后&#xff0c;通过java -jar 启动项…...

编程日记 2025/8/2 17:17:28

17.Chromium指纹浏览器开发教程之设备内存和处理器指纹定制

设备内存指纹定制 在 JavaScript 中&#xff0c;可以使用 navigator.deviceMemory 来获取设备的内存信息。它返回一个表示设备的内存大小&#xff08;以 GB 为单位&#xff09;的浮点数。具体代码如下&#xff1a; if (navigator.deviceMemory) {// 获取设备内存信息const de…...

编程日记 2025/8/3 6:37:23

遇到QT进程启动失败。被调用的程序丢失，或者您可能没有足够的权限来调用该程序。

【完整错误】16:43:40: The process failed to start. Either the invoked program "/home/xiaojin/QT_code/QT_TCP_CLIENT/build/Desktop_Qt_5_15_0_GCC_64bit-Debug/QT_TCP_CLIENT" is missing, or you may have insufficient permissions to invoke the program. …...

编程日记 2025/8/3 6:36:59

大数据可能出现的bug之flume

一、vi /software/flume/conf/dir_to_logger.conf配置文件 问题的关键: Dir的D写成了小写 另一个终端里面的东西一直在监听状态下无法显示 原来是vi /software/flume/conf/dir_to_logger.conf里面的配置文件写错了 所以说不是没有source参数的第三行的原因 跟这个没关系 …...

编程日记 2025/8/3 6:39:14

32-工艺品商城小程序

技术&#xff1a; 基于 B/S 架构 SpringBootMySQLvueelementuiuniapp 环境&#xff1a; Idea mysql maven jdk1.8 node 可修改为其他类型商城 用户端功能 1.系统首页展示轮播图及工艺品列表 2.分类模块:展示产品的分类类型 3.购物车:进行商品多选结算 或者批量管理操作 4.…...

编程日记 2025/8/3 6:37:20

Kubernetes控制平面组件：调度器Scheduler（一）

云原生学习路线导航页&#xff08;持续更新中&#xff09; kubernetes学习系列快捷链接 Kubernetes架构原则和对象设计&#xff08;一&#xff09;Kubernetes架构原则和对象设计&#xff08;二&#xff09;Kubernetes架构原则和对象设计&#xff08;三&#xff09;Kubernetes控…...

编程日记 2025/8/3 1:54:53

HTTP：十.cookie机制

Cookie概念及类型 HTTP cookie，简称cookie，又称数码存根、“网站／浏览＋魔饼／魔片”等，是浏览网站时由网络服务器创建并由网页浏览器存放在用户计算机或其他设备的小文本文件。Cookie使Web服务器能在用户的设备存储状态信息（如添加到在线商店购物车中的商品）或跟踪用户…...

编程日记 2025/8/3 6:43:39

go语言对http协议的支持

http&#xff1a;无状态协议&#xff0c;是互联网中使用http使用http实现计算机和计算机之间的请求和响应 使用纯文本方式发送和接受协议数据&#xff0c;不需要借助专门工具进行分析就知道协议中的数据 服务器端的几个概念 Request&#xff1a;用户请求的信息&#xff0c;用…...

编程日记 2025/8/2 16:52:41

Origin将双Y轴柱状图升级为双向分组柱状图

当变量同时存在两个数值时的可视化时&#xff0c;往往会想到用双Y轴柱状图来表达我们的数据。 双Y轴柱状图是一种在同一图表中使用左右两个Y轴的可视化形式&#xff0c;常用于展示两组量纲不同或数值范围差异较大的数据。 双向分组柱状图是一种结合了双向柱状图和分组柱状图的…...

编程日记 2025/8/3 6:39:13

FileZilla“服务器发回了不可路由的地址，使用服务器地址代替

问题&#xff1a;在宝塔创建的FTP无法使用&#xff0c;提示“服务器回应不可路由的地址。使用服务器地址代替 第一种解决办法&#xff1a;由于宝塔把FTP被动模式端口范围设置成了39000-40000&#xff0c;所以只需要把阿里云服务器上相应的端口范围开放即可。 第二种解决办法&am…...

编程日记 2025/8/3 1:23:02

Linux中服务器时间同步

简单介绍 在 redhat 8 之前&#xff0c;时间同步服务是使用 NTP&#xff08;网络时间协议&#xff09;来实现的&#xff0c;在 redhat 8 及之 后使用是 NTP 的实现工具 chrony 来实现时间同步。 在 redhat 8 及之后&#xff0c;默认情况下已经安装好 chrony 软件并已经开机启…...

编程日记 2025/8/3 6:36:31

gbase8s之线程状态详解（超值）

--mutex wait nsf.0lock 意味着数据库服务器中的一个线程当前正在等待获取名为 nsf.0lock 的互斥锁 可能的原因和影响： 锁争用 (Lock Contention): 这是最常见的原因。多个线程可能需要频繁访问由 nsf.0lock 保护的共享资源。如果持有锁的线程执行时间过长，或者有太多线…...

编程日记 2025/7/29 1:35:18

Linux学习——Linux进程间通信（IPC）聊天程序实践

Linux学习——Linux进程间通信&#xff08;IPC&#xff09;聊天程序实践 一、在阿里云服务器上使用talk程序 Linux系统自带的talk命令可以让两个登录用户进行实时文字聊天&#xff1a; 用户A执行&#xff1a;talk usernameB用户B会收到通知&#xff0c;并需要执行&#xff1…...

编程日记 2025/7/31 22:07:45

PCA 降维实战：从原理到电信客户流失数据应用

一、简介 在机器学习领域&#xff0c;数据的特征维度往往较高&#xff0c;这不仅会增加计算的复杂度&#xff0c;还可能导致过拟合等问题。主成分分析&#xff08;Principal Component Analysis&#xff0c;简称 PCA&#xff09;作为一种经典的降维技术&#xff0c;能够在保留数…...

编程日记 2025/8/3 5:16:54

即插即用模块(1) -MAFM特征融合

(即插即用模块-特征处理部分) 一、(2024) MAFM&MCM 特征融合特征解码 paper&#xff1a;MAGNet: Multi-scale Awareness and Global fusion Network for RGB-D salient object detection 1. 多尺度感知融合模块 (MAFM) 多尺度感知融合模块 (MAFM) 旨在高效融合 RGB 和深度…...

编程日记 2025/7/30 14:34:34

Linux学习——TCP

一.TCP编程API 1.socket函数 1.socket函数 include include int socket(int domain,int type,int protocol); 参数 domain AF_INET AF_INET6 AF_UNIX,AF_LOCAL AF_NETLINK AF_PACKET type SOCK_STREAM: 流式…...

编程日记 2025/8/2 20:04:11

Kubernetes控制平面组件：调度器Scheduler（二）

云原生学习路线导航页&#xff08;持续更新中&#xff09; kubernetes学习系列快捷链接 Kubernetes架构原则和对象设计&#xff08;一&#xff09;Kubernetes架构原则和对象设计&#xff08;二&#xff09;Kubernetes架构原则和对象设计&#xff08;三&#xff09;Kubernetes控…...

编程日记 2025/8/2 22:32:03

数据通信学习笔记之OSPF其他内容2

OSPF 与 BFD 联动 网络上的链路故障或拓扑变化都会导致设备重新进行路由计算&#xff0c;所以缩短路由协议的收敛时间对于提高网络的性能是非常重要的。 OSPF 与 BFD 联动就是将 BFD 和 OSPF 关联起来&#xff0c;一旦与邻居之间的链路出现故障&#xff0c;BFD 对完品以&…...

编程日记 2025/7/30 4:45:36

数据通信学习笔记之OSPF的区域

OSPFArea 用于标识一个 OSPF 的区域 区域是从逻辑上将设备划分为不同的组&#xff0c;每个组用区域号 (Area ID)来标识 OSPF 的区域 ID 是一个 32bit 的非负整数&#xff0c;按点分十进制的形式(与 IPV4 地址的格式一样)呈现&#xff0c;例如 Area0.0.0.1。 为了简便起见&#…...

编程日记 2025/8/1 14:36:52

css3新特性第四章(渐变)

渐变 线性渐变 径向渐变 重复渐变 使用&#xff1a; background-image: xx 渐变 background-image: linear-gradient(red,yellow,green); 公共代码 .box {width: 300px;height: 200px;border: 1px solid black;float: left;margin-left: 30px;margin-top: 30px;text-align:…...

编程日记 2025/8/2 7:28:42

玩机搞机基本常识-------小米OLED屏幕机型怎么设置为永不休眠_手机不息屏_保持亮屏功能 拒绝“烧屏” ？

前面在帮一位粉丝解决小米OLED机型在设置----锁屏下没有永不休眠的问题。在这里&#xff0c;大家要明白为什么有些小米机型有这个设置有的没有的原因。区分OLED 屏幕和 LCD屏幕的不同。从根本上拒绝烧屏问题。 OLED 屏幕的一些优缺点&#x1f49d;&#x1f49d;&#x1f49d; …...

编程日记 2025/7/31 1:42:48

深拷贝和浅拷贝的区别

浅拷贝&#xff1a; 只复制原对象的基本数据类型字段&#xff0c;拥有相对独立的副本数据&#xff0c;修改时不会影响到原对象的字段值。对于原对象的引用数据类型字段&#xff0c;直接共享原对象字段的引用&#xff0c;修改自己的字段时会同时影响原对象。 深拷贝&#xff1a…...

编程日记 2025/8/2 17:17:37

RabbitMQ和Seata冲突吗？Seata与Spring中的事务管理冲突吗

1. GlobalTransactional 和 Transactional 是否冲突&#xff1f; 答&#xff1a;不冲突&#xff0c;它们可以协同工作&#xff0c;但作用域不同。 Transactional: 这是 Spring 提供的注解&#xff0c;用于管理单个数据源内的本地事务。在你当前的 register 方法中&#xff0c…...

编程日记 2025/7/30 3:56:40

[安全实战]逆向工程核心名词详解

逆向工程核心名词详解 一、调试与执行类 1. 断点&#xff08;Breakpoint&#xff09; 定义&#xff1a;在代码中设置标记&#xff0c;使程序执行到此处时暂停类型&#xff1a; 普通断点&#xff1a;通过INT3指令实现条件断点&#xff1a;满足特定条件时触发内存断点&#xf…...

编程日记 2025/8/2 18:35:07

用键盘实现控制小球上下移动——java的事件控制

本文分享Java的一个有趣小项目&#xff0c;实现用键盘控制小球的移动 涉及java知识点&#xff1a;Swing GUI框架&#xff0c;绘图机制&#xff0c;事件处理&#xff0c;焦点控制 1.编写窗口和面板 (1.)定义面板类 Panel 继承自Java 自带类JPanel (2.)定义窗口类 window 继承…...

编程日记 2025/8/1 20:55:17

AutoSAR从概念到实践系列之MCAL篇(二)——Mcu模块配置及代码详解(上)

欢迎大家学习我的《AutoSAR从概念到实践系列之MCAL篇》系列课程，我是分享人M哥，目前从事车载控制器的软件开发及测试工作。 学习过程中如有任何疑问，可底下评论！ 如果觉得文章内容在工作学习中有帮助到你，麻烦点赞收藏评论+关注走一波！感谢各位的支持！ 根据上一篇内容中…...

编程日记 2025/7/29 1:35:14

BEVDet: High-Performance Multi-Camera 3D Object Detection in Bird-Eye-View

背景 在自动驾驶场景下&#xff0c;以往工作是目标检测任务用图像视角做&#xff0c;语义分割用BEV视角做。本文提出了BEVDet&#xff0c;实现了一个统一的框架&#xff0c;它模块化设计分为图像编码器&#xff0c;视角转换器&#xff0c;BEV编码器以及BEV空间的3D检测头。然而…...

编程日记 2025/7/30 12:47:03

高效获取淘宝实时商品数据：API 接口开发与数据采集实战指南

在电商行业竞争白热化的当下&#xff0c;实时且准确的商品数据是企业制定营销策略、优化产品布局的重要依据。淘宝作为国内头部电商平台&#xff0c;其海量的商品数据蕴含着巨大价值。通过 API 接口高效获取淘宝实时商品数据&#xff0c;成为电商从业者和开发者的必备技能。本文…...

编程日记 2025/7/28 23:31:24