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

c++线段树之单点修改区间最大子段和-----P4513 小白逛公园

news 来源：原创 2025/6/5 17:44:17

题目大意

单点修改
查询区间最大字段和

解题思路

如果线段树节点存储的是‘区间最大子段和’，如何合并？
简单的加法或求极值都不行，仔细分析可得，父节点最大字段和可能为：

左子树最大子段和
右子树最大子段和
左子树最大后缀和+右子树最大前缀和

数据结构

线段树存储：

区间总和
区间最大前缀和
区间最大后缀和
区间最大子段和

实现细节

合并操作：在构建和更新线段树时，合并左右子节点的信息，以维护当前节点的四个值。

查询操作：递归查询区间，合并结果时考虑左右子区间的不同情况，确保正确计算最大子段和。

// P4513 小白逛公园, 单点修改，区间查最大子段和
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
#define INF 1000000000
#define MANX 2000002
#define lson (root*2)
#define rson (root*2+1)struct Node {int total; // 区间和int prefix; // 最大前缀和int suffix; // 最大后缀和int max_sum; // 最大字段和
} sgmt[MANX];void push_up(int root) {sgmt[root].total = sgmt[lson].total + sgmt[rson].total;sgmt[root].prefix = max(sgmt[lson].prefix, sgmt[lson].total+sgmt[rson].prefix);sgmt[root].suffix = max(sgmt[rson].suffix, sgmt[rson].total+sgmt[lson].suffix);sgmt[root].max_sum = max({sgmt[lson].max_sum, sgmt[rson].max_sum, sgmt[lson].suffix+sgmt[rson].prefix});
}void update(int a, int b, int l, int r, int root) {if (l == r) {sgmt[root].total = sgmt[root].prefix = sgmt[root].suffix = sgmt[root].max_sum = b;return;}int mid = (l+r)/2;if (a <= mid)  update(a,b,l,mid,lson);else update(a,b,mid+1,r,rson);push_up(root);
}Node query(int a, int b, int l, int r, int root) {if (a <= l && r <= b) return sgmt[root];Node left = {0,-INF,-INF,-INF}, right = {0,-INF,-INF,-INF};int mid = (l+r)/2;if (a <= mid) left = query(a,b,l,mid,lson);if (b > mid) right = query(a,b,mid+1,r,rson);if (left.max_sum == -INF) return right;if (right.max_sum == -INF) return left;Node merged;merged.total = left.total + right.total;merged.prefix = max(left.prefix, left.total+right.prefix);merged.suffix = max(right.suffix, right.total+left.suffix);merged.max_sum = max({left.max_sum, right.max_sum, left.suffix+right.prefix});return merged;
}void build(int l, int r, int root) {if (l == r) return;int mid = (l+r)/2;build(l, mid, lson);build(mid+1, r, rson);push_up(root);
}int main() {ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);int n, m; cin >> n >> m;int npot = 1<<(int)ceil(log2(n));for (int i = 0; i < npot; ++i)if (i < n) {cin >> sgmt[npot+i].total;sgmt[npot+i].prefix = sgmt[npot+i].suffix = sgmt[npot+i].max_sum = sgmt[npot+i].total;} else {sgmt[npot+i].prefix = sgmt[npot+i].suffix = sgmt[npot+i].max_sum = -INF; // 无效值}int left = 1, right = npot, root = 1;build(left, right, root);while (m--) {int op, a, b;cin >> op >> a >> b;if (op == 1) {if (a > b) swap(a, b);Node res = query(a, b, left, right, root);cout << res.max_sum << '\n';} else {update(a, b, left, right, root);}}return 0;

c++线段树之单点修改区间最大子段和-----P4513 小白逛公园

题目大意单点修改查询区间最大字段和解题思路如果线段树节点存储的是‘区间最大子段和’，如何合并？ 简单的加法或求极值都不行，仔细分析可得，父节点最大字段和可能为： 左子树最大子段和右子树最大子段和左子树最…...

编程日记 2025/5/29 13:52:47

[Java实战]Spring Boot整合Elasticsearch（二十六）

[Java实战]Spring Boot整合Elasticsearch（二十六） 摘要：本文通过完整的实战演示，详细讲解如何在Spring Boot项目中整合Elasticsearch，实现数据的存储、检索和复杂查询功能。包含版本适配方案、Spring Data Elasticsea…...

编程日记 2025/5/29 19:30:58

【深度学习新浪潮】大模型在哪些垂域已经有比较好的落地？

AI大模型在多个垂直领域已实现显著落地，以下结合可验证案例与行业数据展开说明：一、医疗健康：精准诊断与个性化治疗呼吸系统疾病诊断国家呼吸医学中心研发的LungDiag模型，基于公开临床数据集训练，在预印本研究中对肺炎、肺癌等10种疾病的辅助诊断准确率达92%。医联Med…...

编程日记 2025/5/28 8:12:36

软件测试全攻略：从概念到实践

目录测试指南针--概念篇 1. 什么是软件测试？ 2. 软件测试和软件开发的关系是什么？ 3. 测试需要哪些能力？ 4. 测试流程是什么样的？ 5. 什么是单元测试和集成测试？ 6. 软件的生命周期是什么样的？ 需求…...

编程日记 2025/5/27 8:03:37

linux hungtask detect机制分析

1，机制概述‌ hungtask detect 是 Linux 内核用于检测长时间阻塞（"hung"）任务的机制，主要针对因死锁、死循环或资源竞争导致无法调度的任务 ‌触发条件‌：任务在 TASK_UNINTERRUPTIBLE 状态持续超过预设阈值…...

编程日记 2025/5/24 20:30:10

影刀处理 Excel：智能工具带来的高效变革

1. 高效的数据处理能力 1.1 快速读取与写入数据影刀在处理 Excel 数据时展现出显著的读取与写入速度优势。传统方法处理大型 Excel 文件时，读取速度可能仅为每秒 100 行左右，而影刀通过优化底层代码和采用高效的文件解析算法，读取速度可达…...

编程日记 2025/5/29 15:18:20

Dashboard - The 2021 Sichuan Provincial Collegiate Programming Contest - Codeforces 过题难度： A K D M H B L 铜奖 5 594 银奖 6 368 金奖 8 755 codeforces.com/gym/103117/problem/A 模拟出牌的过程，打表即可 // Code Start Here int t…...

编程日记 2025/5/24 0:58:35

HarmonyOS 影视应用APP开发--配套的后台服务go-imovie项目介绍及使用

网上有小伙伴对影视应用感兴趣，也想搞个自己的免费观影APP玩玩儿。前期博主开源的有uniapp版本和harmonyOS原生版本影视客户端，但是对博主开源的这个影视后台接口服务不太了解，不知道怎么用起来。这里总结介绍下该go-imove后台接口服务项目介…...

编程日记 2025/6/1 9:05:43

JAVA SE 多线程(上)

文章目录 📕1. Thread类及常见方法✏️1.1 创建线程✏️1.2 Thread 的常见构造方法✏️1.3 Thread 的几个常见属性✏️1.4 启动一个线程---start()✏️1.5 中断一个线程---interrupt()✏️1.6 等待一个线程---join()✏️1.7 获取当前线程引用✏️1.8 休眠当前线程 &…...

编程日记 2025/5/28 0:31:41

基于Bootstrap 的网页html css 登录页制作成品

目录前言一、网页制作概述二、登录页面 2.1 HTML内容 2.2 CSS样式三、技术说明书四、页面效果图前言 ‌Bootstrap‌是一个用于快速开发Web应用程序和网站的前端框架，由Twitter的设计师Mark Otto和Jacob Thornton合作开发。它基于HTML、CSS和JavaScri…...

编程日记 2025/5/31 15:02:56

AUTOSAR图解==＞AUTOSAR_SRS_Transformer

AUTOSAR Transformer 详解基于AUTOSAR标准的Transformer组件技术解析目录 1. AUTOSAR Transformer 概述 1.1 Transformer的作用1.2 Transformer在AUTOSAR中的位置2. Transformer架构设计 2.1 整体架构2.2 类结构设计2.3 交互流程3. Transformer类型与实现 3.1 SOME/IP Transf…...

编程日记 2025/5/29 15:23:26

iOS APP启动页及广告页的实现

iOS APP启动页及广告页的实现涉及UI布局、数据加载、倒计时控制、广告跳转等多个关键环节。以下是我的一些使用心得： 1. UI实现方案双Window方案原理：同时创建两个Window，主Window位于底层，广告Window覆盖在其上。通过切换mak…...

编程日记 2025/5/28 17:54:59

图绘Linux：基础指令脉络阁

目录 Linux命令行介绍目录操作 ls 目录所含文件信息 ls 常用选项 pwd 在那个目录下 cd 进入目录 mkdir 创建目录文件操作 touch 创建普通文件 echo向文件写入 cat 输出文件内容 cp 拷贝文件/目录 mv剪切重命名 rm 删除文件/目录查找 * 匹配符 man 查找指令 …...

编程日记 2025/5/28 17:22:39

数字格式化库 accounting.js的使用说明

accounting.js 是一个用于格式化数字、货币和金额的轻量级库，特别适合财务和会计应用。以下是其详细使用说明： 安装与引入通过 npm 安装： bash 复制下载 npm install accounting 引入： javascript 复制下载 const accounting …...

编程日记 2025/5/31 8:05:09

ngx_http_proxy_protocol_vendor_module 模块

一、前置要求启用 PROXY 协议在 listen 指令中添加 proxy_protocol 参数，例如： server {listen 80 proxy_protocol;listen 443 ssl proxy_protocol;… }商业订阅本模块仅在 Nginx 商业版中提供。二、示例配置 http {# 将 GCP 的 PSC 连接 ID 添…...

编程日记 2025/5/26 6:38:14

C++11-(2)

文章目录 （一）C11新增功能1.1 引用折叠1.1.1 在模板中使用引用折叠的场景1.1.2 引用折叠是如何实现的 1.2 完美转发1.3 lambda表达式语法1.3.1 定义1.3.2 lambda的使用场景1.3.3 捕捉列表1.3.4 mutable语法1.3.5 lambda的原理 （一&#xff09…...

编程日记 2025/5/27 8:11:20

LeetCode算法实战 - - - 双指针与移除元素、快慢指针与删除有序数组中的重复项

LeetCode算法实战 - - - 双指针与移除元素、快慢指针与删除有序数组中的重复项第一题 - - - 移除元素方法一 - - - 双重循环方法二 - - - 双指针方法三 - - - 相向双指针（面对面移动） 第二题 - - -…...

编程日记 2025/5/26 7:31:00

QT6 源（106）：阅读与注释重要的基类控件 QWidget，这是其精简版，完整注释版为篇 37

（1）原篇幅 37 为最开始整理，整理的不是太完善。重点不突出。故重新整理，但删除了大量的注释，重在突出本 QWidget类的内部逻辑，更易观察其包含了哪些内容。至于不理解的成员函数与属性，内容已不太…...

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

【Bluedroid】蓝牙HID DEVICE错误报告处理全流程源码解析

本文基于Android蓝牙协议栈代码，深入解析HID设备在接收非法指令（如无效的SET_REPORT）时的错误处理全流程，涵盖错误映射、协议封装、传输控制三大核心模块。重点剖析以下机制： HID协议规范错误码的动态转换策略控制通…...

编程日记 2025/5/27 7:04:52

Day29 类的装饰器

类也有修饰器，他的逻辑类似：接收一个类，返回一个修改后的类。例如添加新的方法或属性（如示例中的 log 方法）。修改原有方法（如替换 init 方法，添加日志）。甚至可以返回一个全新的类…...

编程日记 2025/5/29 18:05:29

学习黑客Active Directory 入门指南（二）

Active Directory 入门指南（二）：深入逻辑结构与物理组件 🌳🏢 大家好！欢迎回到 “Active Directory 入门指南” 系列的第二篇。在上一篇中，我们初步认识了Active Directory，了解了其…...

编程日记 2025/5/28 14:53:14

为什么el-select组件在下拉选择后无法赋值

为什么el-select组件在下拉选择后无法赋值 https://blog.csdn.net/ZHENGCHUNJUN/article/details/127325558 这个链接解决了大模型无法解决的问题大模型能够写基础且高级一些的代码，但是遇到再深入一些的问题，还是得问百度。对于我这种小白来说问题原因…...

编程日记 2025/6/1 12:37:43

FreeRTOS的学习记录（临界区保护，调度器挂起与恢复）

临界区在 FreeRTOS 中，临界区（Critical Section） 是指程序中一段必须以原子方式执行的代码区域，在此区域内不允许发生任务切换或中断干扰，以保护共享资源或执行关键操作。FreeRTOS 提供了多种机制来实现临界区&#…...

编程日记 2025/6/3 9:06:59

给个人程序加上MCP翅膀

背景最近MCP这个词真是到处都是，看起来特别高大上。我平时没事的时候也一直在关注这方面的技术，知道它是怎么一回事，也懂该怎么去实现。但可惜一直抽不出时间来自己动手搞一个MCP服务。网上关于MCP的教程一搜一大把，但基本上都是…...

编程日记 2025/5/28 15:52:21

2023年河南CCPC（ABCEFHK）

文章目录 2023河南CCPCA. 小水獭游河南(字符串)B. Art for Rest(数组切割)C. Toxel与随机数生成器(水)E. 矩阵游戏（dp）F. Art for Last(区间最小差分)H. Travel Begins(数学思维)K. 排列与质数（规律）总结 2023河南CCPC A. 小水獭…...

编程日记 2025/5/25 11:59:33

【 Redis | 实战篇秒杀优化】

目录前言： 1.分布式锁 1.1.分布式锁的原理与方案 1.2.Redis的String结构实现分布式锁 1.3.锁误删问题 1.4.锁的原子性操作问题 1.5.Lua脚本解决原子性问题 1.6.基于String实现分布式锁存在的问题 1.7.Redisson分布式锁 2.秒杀优化 3.秒杀的异步优化 3.1…...

编程日记 2025/5/27 7:48:52

【Spring】核心机制：IOC与DI深度解析

目录 1.前言 2.正文 2.1三层架构 2.2Spring核心思想（IOC与AOP） 2.3两类注解：组件标识与配置 2.3.1五大类注解 2.3.1.1Controller 2.3.1.2Service 2.3.1.3Repository 2.3.1.4Configuration 2.3.1.5Component 2.3.2方法注解&#x…...

编程日记 2025/5/29 10:29:07

1-机器学习的基本概念

文章目录一、机器学习的步骤Step1 - Function with unknownStep2 - Define Loss from Training DataStep3 - Optimization 二、机器学习的改进Q1 - 线性模型有一些缺点Q2 - 重新诠释机器学习的三步Q3 - 机器学习的扩展Q4 - 过拟合问题（Overfitting） 一、…...

编程日记 2025/5/26 10:42:02

ARM A64 STR指令

ARM A64 STR指令 1 STR (immediate)1.1 Post-index1.1.1 32-bit variant1.1.2 64-bit variant 1.2 Pre-index1.2.1 32-bit variant1.2.2 64-bit variant 1.3 Unsigned offset1.3.1 32-bit variant1.3.2 64-bit variant 1.4 Assembler symbols 2 STR (register)2.1 32-bit varia…...

编程日记 2025/5/26 7:42:01

题目大意

解题思路

数据结构

线段树存储：

实现细节

相关文章：