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

线段树(点修，区查，区修)

news 来源：原创 2025/5/9 23:34:09

文章目录

什么是线段树？
线段树能够解决什么样的问题？
- 模板

什么是线段树？

线段树是一种二叉搜索树，而二叉搜索树，首先满足二叉树，即每个结点最多有两颗子树，并且是一颗搜索树，我们要知道，线段树的每个结点都存储了一个区间，也可以理解成一个线段，而搜索，就是在这些线段上进行搜索操作得到你想要的答案。

线段树能够解决什么样的问题？

线段树的适用范围很广，可以在线维护修改以及查询区间上的最值，求和。对于线段树来说，每次更新以及查询的时间复杂度为O(logN)。

模板

pushdown函数 (一般做一个重载) 作用: 由父亲节点维护子节点, 下放懒标记.
当操作的区间需要分裂时调用. (在modify和ask函数中)
pushup函数 (根据需要选择是否重载)(是否维护多种信息) 作用: 由子节点维护父亲节点.
当子节点改变时, 需要调用, 以保证父亲节点信息正确
build函数, 建树, 推荐将树中的所有数据都手动进行初始化, 避免可能因多组输入产生的错误
update函数, 修改函数. 在进行区间修改的时候, 区间分裂时不要忘记pushdown, 修改后应pushup
query函数, 询问函数, 当遇到区间合并问题时, 应当返回类型为节点类型.

/* 基础数据结构 */
int w[200010];//初始化的值
struct asd{int l,r; //维护区间int sum;//维护的属性int add;//懒标记, 当前节点的懒标记不包括自己.
}p[1000010];//节点数组 void pushup(int x)//向上更新父节点sum值
{p[x].sum=p[2*x].sum+p[2*x+1].sum;
}void bulid(int x,int l,int r)//x表示根节点，l左区间，r右区间
{p[x]={l,r,w[l]};//初始化节点if(l==r)return;是叶子节点则返回int mid=(l+r)/2;不是则裂开bulid(2*x,l,mid);bulid(2*x+1,mid+1,r);pushup(x); 
}void update(int x,int t,int k)//x表示根节点，t表示要修改的原数组，k表示要修改的值
{if(p[x].l==t&&p[x].r==t)找到修改{p[x].sum+=k;return;}int mid=(p[x].l+p[x].r)/2;反之裂开找if(t<=mid)update(2*x,t,k);if(t>mid)update(2*x+1,t,k);pushup(x);
}int query(int x,int l,int r)
{int ma=0;if(l<=p[x].l&&p[x].r<=r)return p[x].sum;pushdown(x);//如果进行区间修改再加这个int mid=(p[x].l+p[x].r)/2;if(l<=mid)ma=max(ma,query(2*x,l,r));if(r>mid)ma=max(ma,query(2*x+1,l,r));return ma;
}void pushdown(int x)向下更新
{if(p[x].add){p[2*x].sum+=(p[2*x].r-p[2*x].l+1)*p[x].add;p[2*x+1].sum+=(p[2*x+1].r-p[2*x+1].l+1)*p[x].add;p[2*x].add+=p[x].add;p[2*x+1].add+=p[x].add;p[x].add=0;}
}void update(int x,int l,int r,int k)//区间和并
{if(l<=p[x].l&&p[x].r<=r){p[x].sum=(p[x].r-p[x].l+1)*k;p[x].add=k;return;}pushdown(x);int mid=(p[x].l+p[x].r)/2;if(l<=mid)update(2*x,l,r,k);if(r>mid)update(2*x+1,l,r,k);pushup(x);
}

线段树(点修，区查，区修)

文章目录什么是线段树？线段树能够解决什么样的问题？模板什么是线段树？ 线段树是一种二叉搜索树，而二叉搜索树，首先满足二叉树，即每个结点最多有两颗子树，并且是一颗搜索树，我们要知…...

编程日记 2025/5/9 23:34:09

深度学习 - 神经网络的原理

## 深度学习 - 神经网络的原理深度学习是机器学习的一个分支，其核心是模拟人脑神经网络的结构和功能，构建多层的神经网络模型，从数据中学习特征并进行预测或分类。 **神经网络的基本原理：** 1. **神经元模型:** * 神经网…...

编程日记 2025/5/9 22:11:28

DeepSeek辅助段落扩写的能力怎么样?

DeepSeek-R1在学术写作的诸多细节层面展现出了显著的应用价值。接下来我们将通过一系列具体案例，深入探讨该工具如何在扩写、翻译、发表以及内容改进等关键环节为学术写作提供有力支持。在提问环节，DeepSeek-R1能够高效地简化提示词，并精准地…...

编程日记 2025/5/9 22:07:16

深入Linux系列之进程地址空间

深入Linux系列之进程地址空间 1.引入那么在之前的学习中，我们知道我们创建一个子进程的话，我们可以在代码层面调用fork函数来创建我们的子进程，那么fork函数的返回值根据我们当前所处进程的上下文是返回不同的值，它在父进程中返…...

编程日记 2025/5/9 18:06:04

虚拟DOM与Diff算法：Vue如何高效更新UI？

虚拟DOM与Diff算法：Vue如何高效更新UI？ 虚拟DOM与Diff算法：Vue如何高效更新UI？什么是虚拟DOM？定义虚拟DOM的优势 Diff算法：如何高效计算UI差异定义核心思想Diff算法的步骤示例代码 Vue中的虚拟DOM与Diff算法…...

编程日记 2025/5/9 22:46:10

Golang 并发机制-6：掌握优雅的错误处理艺术

并发编程可能是提高软件系统效率和响应能力的一种强有力的技术。它允许多个工作负载同时运行，充分利用现代多核cpu。然而，巨大的能力带来巨大的责任，良好的错误管理是并发编程的主要任务之一。并发代码的复杂性并发编程增加了顺序程序所不…...

编程日记 2025/5/9 22:34:10

【MySQL】第二弹---数据库基础全解析：从概念到实践的深度探索

✨个人主页： 熬夜学编程的小林 💗系列专栏： 【C语言详解】【数据结构详解】【C详解】【Linux系统编程】【MySQL】目录 1. 数据库基础 1.1 什么是数据库 1.2 主流数据库 1.3 基本使用 1.3.1 MySQL安装 1.3.2 连接服务器 1.3.3 服务器…...

编程日记 2025/5/9 23:15:28

c++计算机教程

目的做出-*/%计算机要求做出可以计算-*/%的计算机实现完整代码 #include<bits/stdc.h> int main() {std::cout<<"加减- 乘* 除/ 取余% \没有了|(因为可以算三位)"<<"\n"<<"提示:每打完一个符号或打完一个数,\…...

编程日记 2025/5/9 22:33:09

win32汇编环境,对话框程序中自定义工具栏的使用示例三

;运行效果 ;win32汇编环境,对话框程序中自定义工具栏的使用示例三 ;这次是竖着的，以下为生成48*48大小的自定义工具栏图标，自已设计图标样式，显得更专业点。 ;原理是，先生成工具栏控件，再生成图像列表，然后弄几个图标加入图像列表，再把图像列表与工具栏控件关联。需留意…...

编程日记 2025/5/5 17:45:59

集合类不安全问题

ArrayList不是线程安全类，在多线程同时写的情况下，会抛出java.util.ConcurrentModificationException异常解决办法： 1.使用Vector（ArrayList所有方法加synchronized，太重） 2.使用Collections.synchronized…...

编程日记 2025/5/9 22:27:42

怎么使用Cursor以及升级Cursor pro会员

什么是cursor Cursor：结合AI技术的代码编辑器，助力开发者提升编码效率与质量。作为Visual Studio Code的一个衍生版本，Cursor继承了其用户熟知的界面和插件兼容性，并加入了革命性的AI特性。这款编辑器自2023年1月推出以来&#x…...

编程日记 2025/5/9 15:58:31

启用gui，启动图形化界面

1、停止服务 2、开启maxscale GUI ，修改主配置文件（增加框框内两行） 3、启动服务注：如果出现以下启动不成功考虑权限问题 4、访问http://ip:8989 用户名/密码：admin/mariadb...

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

03-移除元素

给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作： 更改…...

编程日记 2025/5/9 13:59:38

LSSVM最小二乘支持向量机多变量多步光伏功率预测（Matlab）

代码下载：LSSVM最小二乘支持向量机多变量多步光伏功率预测（Matlab） LSSVM最小二乘支持向量机多变量多步光伏功率预测一、引言 1.1、研究背景与意义随着全球能源危机和环境问题的日益严重，可再生能源的开发利用成为了世界各国…...

编程日记 2025/5/9 13:25:28

使用Vue开发可复用的Web Components：跨框架组件封装指南

使用Vue开发可复用的Web Components：跨框架组件封装指南使用Vue开发可复用的Web Components：跨框架组件封装指南引言什么是Web Components？为什么选择Vue开发Web Components？ 封装跨框架组件的步骤1. 创建基本的Vue组件2. 将Vue组…...

编程日记 2025/5/8 20:34:14

用AI写游戏1——js实现贪吃蛇

使用模型通义千问提示词： 用js html css 做一个贪吃蛇的动画 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><title>Snake Game</title><link rel"stylesheet" href"c…...

编程日记 2025/5/9 13:26:23

星闪开发入门级教程之安装编译器与小项目烧录

系列文章目录星闪开发入门级教程好久不见，已经好几年没有发文章了，星闪-作为中国原生的新一代近距离无线联接技术品牌。我想着写点东西。为了适合新手，绝对小白文。文章目录系列文章目录前言一、Hispark Studio1.安装Hispark Studio2.安…...

编程日记 2025/5/9 16:09:33

java求职学习day32

JavaScript 详解课程目标： 1 、 JavaScript 介绍 2 、 HTML 和 JavaScript 结合方式 3 、 JavaScript 的使用 4 、 DOM 操作 5 、 BOM 操作 1. JavaScript介绍 (1)虽然是 java 作为前缀，但 java 和 javascript 的关系，就像老婆和老婆…...

编程日记 2025/5/9 15:11:28

【Markdown语法】锚点机制：跳转任意位置

最近写文章时，发现有一个需求：想要实现一种点击跳转到文档中任意位置的功能，这就是锚点机制，就像游戏中的传送锚点，于是写成文章记录一下使用方式。本文将详细介绍如何使用Markdown创建文档内部跳转（即锚…...

编程日记 2025/5/9 15:34:29

Docker安装pypiserver私服

Docker安装pypiserver私服 1 简介 Python开源包管理工具有pypiserver、devpi和Nexus等，pypiserver安装部署比较简单，性能也不错。搭建pypiserver私服，可以自己构建镜像，也可以使用官网的docker镜像。 # Github地址 https://g…...

编程日记 2025/5/9 9:25:28

基于微信小程序的居住证申报系统设计与实现（LW+源码+讲解）

专注于大学生项目实战开发,讲解,毕业答疑辅导，欢迎高校老师/同行前辈交流合作✌。技术范围：SpringBoot、Vue、SSM、HLMT、小程序、Jsp、PHP、Nodejs、Python、爬虫、数据可视化、安卓app、大数据、物联网、机器学习等设计与开发。主要内容：…...

编程日记 2025/5/9 10:49:37

网站改HTTPS方法

默认的网站建设好后打开的样子那看起来像是钓鱼网站，现在的浏览器特别只能，就是你新买来的电脑默认的浏览器同样也会出现这样“不安全”提示。传输协议启动了向全球用户安全传输网页内容的流程。然而，随着HTTPS的推出，传输协议通…...

编程日记 2025/5/1 22:49:00

什么是三层交换技术？与二层有什么区别？

什么是三层交换技术？让你的网络飞起来！ 一. 什么是三层交换技术？二. 工作原理三. 优点四. 应用场景五. 总结前言点个免费的赞和关注，有错误的地方请指出，看个人主页有惊喜。作者：神的孩子都在歌唱大家好…...

编程日记 2025/5/9 13:42:16

极客说｜利用 Azure AI Agent Service 创建自定义 VS Code Chat participant

作者：卢建晖 - 微软高级云技术布道师「极客说」是一档专注 AI 时代开发者分享的专栏，我们邀请来自微软以及技术社区专家，带来最前沿的技术干货与实践经验。在这里，您将看到深度教程、最佳实践和创新解决方案。关注「极客说」&a…...

编程日记 2025/5/9 13:52:41

Rust语言进阶之标准输入: stdin用法实例(一百零五)

简介： CSDN博客专家、《Android系统多媒体进阶实战》一书作者新书发布：《Android系统多媒体进阶实战》🚀 优质专栏： Audio工程师进阶系列【原创干货持续更新中……】🚀 优质专栏： 多媒体系统工程师系列【…...

编程日记 2025/5/9 14:29:09

力扣刷题思路

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档文章目录前言递归70. 爬楼梯112. 路径总和509. 斐波那契数分治169. 多数元素240.搜索二维矩阵 II --- 二分查找单调栈 ---「找最近一个比当前值大/小」的问题739. 每日温度…...

编程日记 2025/5/9 13:45:43

一、搭建实验拓扑图二、基本设备配置设备接口IP地址子网掩码网关PC1E0/0/110.0.1.1255.255.255.0N/APC2E0/0/110.0.1.2255.255.255.0N/APC3E0/0/110.0.1.3255.255.255.0N/APC4E0/0/110.0.1.4255.255.255.0N/APC5E0/0/110.0.1.6255.255.255.0N/Aserver-1E0/0/110.0.1.5255.2…...

编程日记 2025/5/9 15:55:28

音频进阶学习十二——Z变换

文章目录前言一、Z变换1.Z变换的作用2.Z变换公式3.Z的状态表示1） r 1 r1 r12） 0 < r < 1 0<r<1 0<r<13） r > 1 r>1 r>1 4.关于Z的解释二、收敛域1.收敛域的定义2.收敛域的表示方式3.ROC的分析1）当 …...

编程日记 2025/5/9 15:58:31

理解推理型大语言模型

构建和改进推理模型的方法与策略本文描述了构建推理模型的四种主要方法，以及我们如何增强大型语言模型（LLM）的推理能力。我希望这能为你提供有价值的见解，并帮助你了解这一领域快速发展的文献和热潮。在2024年，LLM…...

编程日记 2025/5/9 14:51:38

【Brinson 绩效归因模型】

Brinson 绩效归因模型 1、前言2、Brinson模型介绍2.1 归因方式2.1.1 BHB 超额收益分解方案2.1.2 BF 超额收益分解方案 2.2 多期 Brinson 模型 1、前言如此之多的基金，收益率各有不同，即使同等收益率的基金也各有不同的成因。在这种形势下，广…...

编程日记 2025/5/9 14:35:39

如何轻松将Matlab生成的图表嵌入PowerPoint演示文稿

文章目录 Matlab将生成的图添加PPT中一、Matlab脚本1.添加图片函数2.使用示例总结 Matlab将生成的图添加PPT中在许多科学、工程和商业领域，Matlab作为一款强大的数值计算和可视化工具，被广泛应用于数据分析和模型构建。然而，当涉及到分享这…...

编程日记 2025/5/9 14:48:55

组合(力扣77)

从这道题开始，我们正式进入回溯算法的学习。之前在二叉树中只是接触到了一丢丢，而这里我们将使用回溯算法解决很多经典问题。那么这道题是如何使用回溯算法的呢？在讲回溯之前，先说明一下此题是如何递归的。毕竟回溯递归不分家&a…...

编程日记 2025/5/9 16:13:24

2.7学习

crypto buu-还原大师仔细阅读题目，这里有一段字符串，但是其中有四个大写字母被替换成了‘？’，那么我们写脚本：首先将四个问号均换成26个大写字母并且组成不同的组合， 所以有四个循环让四个问号都遍历26个…...

编程日记 2025/5/9 16:11:25

[开源/教程]使用Ollama+ESP32实现本地对话助手(可接入deepseek等模型)

[开源/视频教程]使用OllamaESP32实现本地对话助手(可接入deepseek等模型) 简介使用ollama实现本地模型的定制, 可以做到数据不泄露以及绕开检测的效果, 之后使用嘉立创的esp32开发板实现简单的对话助手同时接入本文档, 可以直接使用AI对话的方式进行文档处理 XuSenfeng/ai…...

编程日记 2025/5/9 4:39:05

Swagger2 自定义排序

分享一下SpringSwagger2在线文档自定义排序的代码。这里参考swagger2 接口排序_swagger接口排序-CSDN博客提供的思路，并在此基础上做了优化。 1、引用pom信息 <dependency><groupId>io.swagger</groupId>&l…...

编程日记 2025/5/9 15:39:58

sentinel的限流原理

Sentinel 的限流原理基于流量统计和流量控制策略，通过动态规则对系统资源进行保护。其核心设计包括以下几个关键点： 流量统计模型：滑动时间窗口 Sentinel 使用滑动时间窗口算法统计单位时间内的请求量，相比传统的固定时间窗…...

编程日记 2025/5/9 15:14:18

Mac 部署Ollama + OpenWebUI完全指南

文章目录 💻 环境说明🛠️ Ollama安装配置1. 安装[Ollama](https://github.com/ollama/ollama)2. 启动Ollama3. 模型存储位置4. 配置 Ollama 🌐 OpenWebUI部署1. 安装Docker2. 部署[OpenWebUI](https://www.openwebui.com/)（可视化…...

编程日记 2025/5/9 13:47:31

C/C++ 面试智能指针

说下你对智能指针的理解回答1: 因为C使用内存的时候很容易出现野指针、悬空指针、内存泄露的问题。所以C11引入了智能指针来管理内存。有四种： auto_ptr：已经不用了unique_ptr：独占式指针，同一时刻只能有一个指针指向同一个对…...

编程日记 2025/5/9 14:56:08

Halcon缓存？内存泄漏？

目录 1、前言 2、图片缓存 3、全局内存缓存 4、临时内存缓存 5、处理 HALCON 中的疑似内存泄漏 6、其他 1、前言除⾮必要，否则不建议修改 HALCON 自带的缓存设置。 2、图片缓存图像通常需要大量内存，而分配大块内存的过程较慢。因此，当释放图像时，HALCON并…...

编程日记 2025/5/9 13:53:34

升级 SpringBoot3 全项目讲解 — 周边店铺展示功能如何实现

学会这款 🔥全新设计的 Java 脚手架 ，从此面试不再怕！ 1. 升级 Spring Boot 到 3.x 在升级 Spring Boot 之前，我们需要确保项目的依赖和配置与新版本兼容。以下是升级的主要步骤： 1.1 更新 pom.xml 文件首先&#…...

编程日记 2025/5/9 13:21:52

Git(分布式版本控制系统)系统学习笔记【并利用腾讯云的CODING和Windows上的Git工具来实操】

Git的概要介绍 1️⃣ Git 是什么？ Git 是一个分布式版本控制系统（DVCS），用于跟踪代码的变更、协作开发和管理项目历史。由 Linus Torvalds（Linux 之父）在 2005 年开发，主要用于代码管理。…...

编程日记 2025/5/9 13:53:34

光学和光子学模拟工具在 AR/VR 中的作用

AR/VR 中的光学和光子学增强现实 (AR) 和虚拟现实 (VR) 站在数字进化的前沿。光学和光子学这一复杂的科学深入研究了光的产生、检测和操控，在这一转变中发挥着至关重要的作用。图 1 (a) 展示了 AR 系统的设计，强调了光学的关键作用。该图描绘了光的旅…...

编程日记 2025/5/9 1:32:32

大模型产品Deepseek（四）、本地安装部署（Ollama方式）

Ollama与DeepSeek的本地安装与部署教程（Windows/MacOS）在许多AI应用场景中，您可能希望将智能模型本地化，以便更高效地处理数据并减少对外部云服务的依赖。本文将介绍如何在Windows和macOS上直接安装和配置Ollama，以及如何基于Ollama平台部署DeepSeek模型并进行本地交互。…...

编程日记 2025/5/7 15:26:17

visual studio安装

一、下载Visual Studio 访问Visual Studio官方网站。下载 Visual Studio Tools - 免费安装 Windows、Mac、Linux 在主页上找到并点击“下载 Visual Studio”按钮。选择适合需求的版本，例如“Visual Studio Community”（免费版本）&#x…...

编程日记 2025/5/9 13:38:58

AI大模型——DeepSeek模型部署实战

摘要文章主要介绍了DeepSeek大模型的本地部署方法、使用方式以及API接入相关内容。首先指出可通过下载Ollama来部署DeepSeek-R1模型，并给出了模型不同参数版本及存储信息。接着说明了如何通过Chatbox官网下载并接入DeepSeek API，以及如何接入本地部署模…...

编程日记 2025/5/2 1:25:46

音视频的文件封装——AVI、MP4、MKV

3.MKV (Matroska Video File) Matroska （俄语： матроска ）是一种多媒体封装格式，可把多种不同编码的影像、不同格式的音频、不同语言的字幕封装到一个文件内。也是一种开放源代码的多媒体封装格式。 Matroska 支持多种文件…...

编程日记 2025/5/9 14:17:11

讯飞绘镜（ai生成视频）技术浅析（五）：视频生成

讯飞绘镜（AI生成视频）是一种先进的AI视频生成技术，能够将静态的分镜画面转换为动态视频，并使画面中的元素按照一定的逻辑和动作进行动态展示。一、讯飞绘镜视频生成技术概述讯飞绘镜的视频生成技术主要包含以下几个核心模块： 1.视频生成模型：包括生成对抗网络（GAN）…...

编程日记 2025/5/9 15:49:12

【FPGA】 MIPS 12条整数指令【3】

实现乘除修改框架 EX：实现带符号乘除法和无符号乘除法 HiLo寄存器：用于存放乘法和除法的运算结果。Hi、Lo为32bit寄存器。电路描述与实现RegFile思想一致仿真代码 DataMem.v include "define.v"; module DataMem(input wire clk,input…...

编程日记 2025/5/6 7:04:40

【补充】RustDesk一键部署及账号登录配置

前言之前分享的配置rustdesk的帖子只是搭建了一个简易服务器，仅能实现简单的远程桌面功能。在后续的使用中切换设备使用时无法看到之前连接的设备，必须知道每个设备的id号，才能在新设备上连接。数据无法在设备间迁移，感觉很麻烦…...

编程日记 2025/5/9 13:56:09

2025.2.6 数模AI智能体大更新，更专业的比赛辅导，同提示词效果优于gpt-o1/o3mini、deepseek-r1满血

本次更新重新梳理了回复逻辑规则，无任何工作流，一共3.2k字细节描述。具体效果可以看视频，同时也比对了gpt-o1、gpt-o3mini、deepseek-r1-67BI，从数学建模题目解答上来看，目前我的数模AI智能体具有明显优势。 AI智能体优…...

编程日记 2025/5/9 13:48:24

文章目录

什么是线段树？

线段树能够解决什么样的问题？

模板

相关文章：