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

线段树,单点,区间修改查阅

news 来源：原创 2025/5/8 3:51:38

#PermanentNotes/algorithm

思想

首先关于树有许多类型,这里我们主要首线段树,整体思想就是将一个大区间进行拆分,拆分成各个小区间,在我们进行查找,更新时,就是对区间的查找更新

类型

初始化,构建树

代码

const int Z = 1e7;
const ll INF = 1e18;
const int maxn= 1e5 + 10;
const int maxnn = maxn << 2;
int N, M, E;ll tree[maxnn];void build(int l, int r, int k) {if (l == r) {tree[k] = INF;//在这里,我经常将它的节点写成它的l return;}int mid = l + r >> 1;int lc = k << 1;int rc = k << 1 | 1;build(l, mid, lc);build(mid + 1, r, rc);tree[k] = min(tree[lc], tree[rc]);
}

在我们的初始化当中,一定要根据题意,确定我们最开始要初始的值(我们假设我们求的是一个区间最小值,那么将每个区间都初始化为最大值)

单点更新

代码

这里,我们假设求最小值


void pushup(int rt)
{tree[rt] = min(tree[rt << 1], tree[rt << 1 | 1]);
}void update(int pos,ll c,int l,int r,int rt)
{if(l==r){tree[rt]=min(tree[rt],c);return ;}int m=(l+r)>>1;if(pos<=m) update(pos,c,lson);if(pos> m) update(pos,c,rson);pushup(rt);
}

区间查找

我们假设查找一个区间的最小值

代码

ll query(int L, int R, int l, int r, int rt)
{if (L <= l && r <= R) {return tree[rt];}int m = (l + r) >> 1;ll ret = inf;int lc=rt<<1;int rc=rt<<1|1;if (L <= m) ret = min(ret, query(L, R, l,m,lc));if (R > m) ret = min(ret, query(L, R, m+1,r,rc));return ret;
}

区间修改(懒标记法)

每次在进行左右区间(lc,rc)操作之前,先进行pushdown对,对lc,rc操作完毕之后再pushup


typedef long long ll;#define lc p<<1
#define rc p<<1|1const int N = 1e5;
int a[N];
struct node {int l;int r;ll sum;ll add;
}tr[4 * N];void pushup(int p) {tr[p].sum = tr[lc].sum + tr[rc].sum;
}
void pushdown(int p) {if (tr[p].add) {tr[lc].sum += (tr[lc].r - tr[lc].l + 1) * tr[p].add;tr[rc].sum += (tr[rc].r - tr[rc].l + 1) * tr[p].add;tr[lc].add += tr[p].add;tr[rc].add += tr[p].add;tr[p].add = 0;}
}void build(int p, int l, int r) {tr[p] = { l,r,a[l],0 };if (l == r)return;int m = l + r >> 1;build(lc, l, m);build(rc, m + 1, r);pushup(p);
}void update(int p, int x, int y, int k) {if (x <= tr[p].l && tr[p].r <= y) {tr[p].sum += (tr[p].r - tr[p].l + 1) * k;tr[p].add += k;return;}int m = tr[p].l + tr[p].r >> 1;pushdown(p);if (x <= m)update(lc, x, y, k);if (m < y)update(rc, x, y, k);pushup(p);
}ll query(int p, int x, int y) {if (x <= tr[p].l && tr[p].r <= y)return tr[p].sum;int m = tr[p].l + tr[p].r >> 1;pushdown(p);ll sum = 0;if (x <= m)sum += query(lc, x, y);if (m < y)sum += query(rc, x, y);return sum;
}

推荐视频b站up董晓算法我的算法都是在这儿学的

线段树例题
acwing243
洛谷p3372
洛谷p3373

线段树,单点,区间修改查阅

#PermanentNotes/algorithm 思想首先关于树有许多类型,这里我们主要首线段树,整体思想就是将一个大区间进行拆分,拆分成各个小区间,在我们进行查找,更新时,就是对区间的查找更新类型初始化,构建树代码 const int Z 1e7; const ll INF 1e18; const int maxn 1e5 10…...

编程日记 2025/5/8 3:51:38

音视频(二)ffmpeg编译及推流

FFmpeg 大名鼎鼎，就不多介绍了 1：环境 win11_amd64 ffpmeg download:https://git.ffmpeg.org/ffmpeg.git ffmpeg msys2 download:https://www.msys2.org/ vs2022 (c 写demo用) 用别的也行 usb2.0 摄像头（有点老） opencv 看上传的…...

编程日记 2025/5/6 8:52:24

syslog 与 Linux 内核日志系统全面解析

在 Linux 系统中，日志是进行系统调试、故障排查和系统安全分析的重要手段。syslog 和内核日志是 Linux 日志组成的核心组件。本文将从原理、实现、配置、常见问题分析等综合解析，全面解读 Linux 下的日志机制。一、syslog 系统概述 1.1 什么是 syslog …...

编程日记 2025/5/8 3:22:09

SQL问题分析与诊断（8）——关键信息（2）

8.2. 关键信息 8.2.2. 警告查询计划中，可能会看到出现于操作符上的小图标，特别是黄色或红色的感叹号。这些图标都是警告。并非每个警告都指示一个严重问题，但发现时请检查该图标的属性窗口，其将包含该警告图标的具体细节。 8.…...

编程日记 2025/5/8 3:14:27

HCIA/HCIP基础知识笔记汇总

HCIA/HCIP基础知识笔记汇总 ICT产业链： 上游：芯片制造、元器件生产、光纤光缆制造中游：硬件组装、软件开发、网络建设维护下游：电信服务、互联网服务、终端产品 VLAN端口类型： access ：…...

编程日记 2025/5/7 5:16:21

vue3 动态路由

定义： 对路由的添加通常是通过 routes 选项来完成的，但是在某些情况下，你可能想在应用程序已经运行的时候添加或删除路由 1. 动态添加路由规则场景在应用初始化时，可能需要根据用户的角色或权限动态添加路由规则。实现 im…...

编程日记 2025/5/8 2:48:27

《Linux内存管理：实验驱动的深度探索》大纲

《Linux内存管理：实验驱动的深度探索》 ——通过递进式实验与问题剖析，从入门到精通第一部分：初探内存——基础概念与简单实验目标：理解内存的基本行为，学会观察和提问第1章内存初体验：从"free…...

编程日记 2025/5/8 2:43:21

【C语言】深入理解指针（五）：sizeof、strlen与数组指针的那些事儿

前言在C语言的学习中，指针始终是一个让人又爱又恨的话题。它强大而灵活，但同时也充满了陷阱。今天，我们就来深入探讨一下指针相关的几个重要知识点：sizeof和strlen的区别，以及数组和指针在笔试题中的那些常见问题。希…...

编程日记 2025/5/8 2:10:30

CMake学习-- install 指令详细说明

目录 CMake中install命令的用法背景知识使用方法项目结构示例代码CMakeLists.txt构建和安装详细介绍安装库和头文件安装可执行文件安装额外的文件安装目录结构使用安装的库总结 CMake中install命令的用法背景知识在软件开发过程中，构建和安装是两个重要的环节…...

编程日记 2025/5/8 1:49:35

Cannot find a valid baseurl for repo: centos-sclo-sclo/x86_64

rpm -Uvh https://repo.zabbix.com/zabbix/5.0/rhel/7/x86_64/zabbix-release-latest-5.0.el7.noarch.rpmyum clean allyum macache fast 编辑配置文件 /etc/yum.repos.d/zabbix.repo and enable zabbix-frontend repository. [zabbix-frontend]...enabled1... 下载相关…...

编程日记 2025/5/8 2:02:24

uniapp 微信小程序使用ucharts

文章目录前言一、组件功能概述二、代码结构分析2.1 模板结构总结前言本文介绍一个基于 Vue 框架的小程序图表组件开发方案。该组件通过 uCharts 库实现折线图的绘制，并支持滚动、缩放、触摸提示等交互功能。文章将从代码结构、核心方法、交互实现和样式设计等方…...

编程日记 2025/5/8 2:52:25

空调开机启动后发出噼里啪啦的异响分析与解决

背景当空调使用时由于制冷或制热运转时（关机后可能也会出现），塑料件热胀冷缩引起，可能会出现“咔咔”的声音；空调冷媒在空调内管路流动时会出现轻微的“沙沙”的声音；也有可能是新装的空调摆风轴出现响声…...

编程日记 2025/5/8 1:20:41

Python爬虫第3节-会话、Cookies及代理的基本原理

目录一、会话和Cookies 1.1 静态网页和动态网页 1.2 无状态HTTP 1.3 常见误区二、代理的基本原理 2.1 基本原理 2.2 代理的作用 2.3 爬虫代理 2.4 代理分类 2.5 常见代理设置一、会话和Cookies 大家在浏览网站过程中，肯定经常遇到需要登录的场景。有些…...

编程日记 2025/5/8 1:16:40

《自然-方法》2024年度技术：空间蛋白质组学（spatial proteomics）

李升伟编译《自然-方法》第21卷 2195-2196页 (2024) 解析组织空间蛋白质组的技术，正成为图谱级研究项目的基石。这些项目正在兑现其承诺，帮助人类理解健康和疾病状态下的生物复杂性。人类天生充满探索欲。我们热爱勘测未知疆域，并随之绘…...

编程日记 2025/5/8 3:14:26

pip安装timm依赖失败

在pycharm终端给虚拟环境安装timm库失败（ pip install timm），提示你要访问 https://rustup.rs/ 来下载并安装 Rust 和 Cargo 直接不用管，换一条命令 pip install timm0.6.13 成功安装简单粗暴...

编程日记 2025/5/8 1:31:49

【工具变量】全国分省低空经济高质量发展数据（2012-2023年）

测算方式：参考CSSCI《北京航空航天大学学报(社会科学版)》沈映春（2024）老师的做法，如商图指标构建图所示。包含内容： 样例代码： 样例数据： 参考文献：沈映春,张豪兴.数字基础设施建设…...

编程日记 2025/5/8 3:15:36

【Kubernetes】如何使用 kubeadm 搭建 Kubernetes 集群？还有哪些部署工具？

使用 kubeadm 搭建 Kubernetes 集群是一个比较常见的方式。kubeadm 是 Kubernetes 提供的一个命令行工具，它可以简化 Kubernetes 集群的初始化和管理。下面是使用 kubeadm 搭建 Kubernetes 集群的基本步骤： 1. 准备工作确保你的环境中有两台或更多的机…...

编程日记 2025/5/7 9:53:22

Java 枚举类 Key-Value 映射的几种实现方式及最佳实践

Java 枚举类 Key-Value 映射的几种实现方式及最佳实践前言在 Java 开发中，枚举(Enum)是一种特殊的类，它能够定义一组固定的常量。在实际应用中，我们经常需要为枚举常量添加额外的属性，并实现 key-value 的映射关系。本文将详细…...

编程日记 2025/5/8 3:33:08

JavaScript instanceof 运算符全解析

JavaScript instanceof 运算符全解析核心语义：判断一个对象（object）是否属于某个构造函数（constructor）或类的实例，基于原型链（prototype chain）实现类型检测。一、JavaScript 中的基础用法 1. 语法结构 object instanceof constructor 返回值：布尔值（true/fal…...

编程日记 2025/5/7 4:44:31

问题大集09-如何实现vite创建的react项目的配置别名路径@

（1）如何实现vite创建的react项目的配置别名路径 1）直接修改 Vite 配置文件 ①打开项目根目录下的 vite.config.js 文件（如果没有则新建），添加 resolve.alias 配置（新增resolve部分）…...

编程日记 2025/5/8 1:54:09

鸿蒙开发_TS快速入门_TS中模块化操作_模块的导入导出---纯血鸿蒙HarmonyOS5.0工作笔记008

然后我们再来看鸿蒙中的模块如何导入导出。其实就跟Java中的import是一个意思的。只不过我们如果想把一个类中的某个方法导入到另一个类中，那么首先要在这个类中去导出这个方法。可以看到导出的关键字是export。然后导入的关键字是import。然后我们写个例子去看一下，…...

编程日记 2025/5/7 15:12:12

算法设计与分析之“分治法”

分治法（Divide and Conquer）是一种高效的算法设计策略，其核心思想是将复杂问题分解为多个子问题，递归求解后再合并结果。以下是分治法的详细介绍： 一、分治法的基本步骤分治法遵循以下三步流程： 分解&…...

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

java 静态内部类

java 静态内部类一、位置二、特点三、静态内部类的实例化四、代码示例一：演示特点一五、代码示例二：演示特点二六、代码实例三：演示特点三七、代码实例四：演示特点四文章同步更新（更好的排版）&#xff1a…...

编程日记 2025/5/8 3:37:07

Axure疑难杂症：完美解决文本框读取、赋值、计数（玩转文本框）

亲爱的小伙伴，在您浏览之前，烦请关注一下，在此深表感谢！ 课程主题：玩转文本框主要内容：文本框读取、赋值、验证、计数应用场景：验证码、文本限制、文本取值、文本赋值等场景案例展示&…...

编程日记 2025/5/5 12:49:47

Python数据可视化-第2章-使用matplotlib绘制简单图表

环境开发工具 VSCode库的版本 numpy1.26.4 matplotlib3.10.1 ipympl0.9.7教材本书为《Python数据可视化》一书的配套内容，本章为第2章使用matplotlib绘制简单图表本文主要介绍了折线图、柱形图或堆积柱形图、条形图或堆积条形图、堆积面积图、直方图、饼图或…...

编程日记 2025/5/8 3:39:38

国产系统服务器识别不到SATA盘

在使用浪潮、海光、华三等系列服务器安装操作系统的时候提示没有足够的存储空间，其实是有两块512的SATA硬盘的，但是他没有识别到。需要给硬盘做raid存储阵列才能让系统识别到他，下面是在BIOS中配置RAID的方法。 1、重启机器，按下…...

编程日记 2025/5/8 1:37:07

解决小程序video控件在真机和上线后黑屏不播放问题

小程序上线后，mp4格式的视频无法点击是黑屏，但是测试得时候在微信开发者工具中能够打开正常播放原因：编码格式不能是vp9 微信开发者工具本地设置中把这个打开勾选。排查：可以换一个视频尝试能不能真机播放，如果能&a…...

编程日记 2025/5/8 1:57:56

Vue3编译器深度解析：从模板编译到极致性能优化

一、编译技术架构演进 1.1 Vue2到Vue3编译架构升级 1.2 编译阶段性能基准对比优化项Vue2编译耗时Vue3编译耗时性能提升模板解析速度12ms/千节点3ms/千节点75%AST遍历速度8ms/层级2ms/层级68%代码生成速度15ms/组件4ms/组件73%内存占用峰值84MB32MB62% 二、模板编译核心过程 …...

编程日记 2025/5/8 2:55:02

Google Gemini 2.0 网页抓取真丝滑

网页抓取从未如此简单——这一切都要归功于谷歌突破性的多模态实时API Gemini 2.0 借助这个工具，你可以毫不费力地从任何网页提取数据，无论页面结构多么复杂、内容多么杂乱无章，或是需要提取非常特定的信息。今天，我将通过自己实…...

编程日记 2025/5/7 14:34:10

Leetcode-100 二分查找常见操作总结

二分查找常见操作总结 1. 基本二分查找目标: 在有序数组 nums 中查找 target 的索引（如果存在）。适用场景: 需要在有序数组中查找某个特定元素。适用于无重复元素的情况。示例: 输入 nums [1, 2, 3, 4, 5], target 3，输出 2。 d…...

编程日记 2025/5/8 3:31:45

Android： Handler 的用法详解

Android 中 Handler 的用法详解 Handler 是 Android 中用于线程间通信的重要机制，主要用于在不同线程之间发送和处理消息。以下是 Handler 的全面用法指南： 一、Handler 的基本原理 Handler 基于消息队列(MessageQueue)和循环器(Looper)工作&#xff…...

编程日记 2025/5/8 3:18:27

第149场双周赛：找到字符串中合法的相邻数字、重新安排会议得到最多空余时间 Ⅰ、

Q1、找到字符串中合法的相邻数字 1、题目描述给你一个只包含数字的字符串 s 。如果 s 中两个相邻的数字满足以下条件，我们称它们是合法的 ： 前面的数字不等于第二个数字。两个数字在 s 中出现的次数恰好分别等于这个数字本身。请你从左到右…...

编程日记 2025/5/8 1:55:08

深入解析Translog机制：Elasticsearch的数据守护者

一、为什么需要Translog？ Elasticsearch的数据写入流程是先写入内存缓冲区，然后定期刷新到磁盘生成Lucene分段。由于内存数据易失性，若在刷新前发生宕机，未持久化的数据将永久丢失。Translog的诞生正是为了解决这一数据可靠性问题…...

编程日记 2025/5/8 3:22:09

音视频入门基础：MPEG2-TS专题（25）——通过FFmpeg命令使用UDP发送TS流

音视频入门基础：MPEG2-TS专题系列文章： 音视频入门基础：MPEG2-TS专题（1）——MPEG2-TS官方文档下载音视频入门基础：MPEG2-TS专题（2）——使用FFmpeg命令生成ts文件音视频入门基础…...

编程日记 2025/5/8 1:45:45

3、nFR52xx蓝牙学习(点亮第一个LED灯)

一、点灯代码： led.h文件 #ifndef __LED_H #define __LED_H#include "nrf52840.h"#define LED_0 NRF_GPIO_PIN_MAP(0,13) #define LED_1 NRF_GPIO_PIN_MAP(0,14) #define LED_2 NRF_GPIO_PIN_MAP(0,15) #define LED_3 …...

编程日记 2025/5/8 1:54:09

符号秩检验

内容来源非参数统计（第2版） 清华大学出版社王星褚挺进编著符号秩检验在符号检验的基础上，增加了数据绝对值大小的信息检验统计量用一个简单的例子来说明样本数据 X i , i 1 , ⋯ , 6 X_i,i1,\cdots,6 Xi,i1,⋯,6 如下 X …...

编程日记 2025/5/6 14:07:10

制造业数字化转型：流程改造先行还是系统固化数据？基于以MTO和MTS的投资回报分析

1. 执行摘要制造业正经历一场深刻的数字化转型，企业面临着先进行流程改造以优化运营，还是直接上线系统以固化数据的战略选择。本文深入分析了以销定产（MTO）和以产定销（MTS）两种主要生产模式下&#xff0c…...

编程日记 2025/4/29 23:42:11

python相关笔记

一。 is和的区别 1.is看的是发票逻辑地址，用来判断两个变量是否引用同一个对象，is关注的是‘身份’ 2.判断两个对象是否具有相同的值，关注的是内容是否相等，也即值是否相等。 3. if x is None: print(x is None")...

编程日记 2025/5/5 0:08:42

C++(匿名函数+继承+多态)

#include <iostream> #include <cstring> #include <cstdlib> #include <unistd.h> #include <sstream> #include <vector> #include <memory>using namespace std;// 基类 Weapon class Weapon { protected:int atk; public:Weapon…...

编程日记 2025/5/6 22:43:57

界面架构 - MVVM (Qt)

MVVM MVVM 的主要特点示例示例功能示例代码ViewModel 类（C）主函数入口（main.cpp） QML 文件（main.qml）总结 MVVM（Model-View-ViewModel）架构是一种旨在进一步分离界面和业务逻辑的设计…...

编程日记 2025/5/4 17:41:30

在未归一化的线性回归模型中，特征的尺度差异可能导致模型对特征重要性的误判

通过数学公式来更清晰地说明归一化对模型的影响，以及它如何改变特征的重要性评估。 1. 未归一化的情况假设我们有一个线性回归模型： y β 0 β 1 x 1 β 2 x 2 ϵ y \beta_0 \beta_1 x_1 \beta_2 x_2 \epsilon yβ0β1x1β2x2ϵ 其…...

编程日记 2025/5/7 2:32:34

【大模型系列篇】大模型基建工程：使用 FastAPI 构建 MCP 服务器

今天我们将使用FastAPI来构建 MCP 服务器，Anthropic 推出的这个MCP 协议，目的是让 AI 代理和你的应用程序之间的对话变得更顺畅、更清晰。FastAPI 基于 Starlette 和 Uvicorn，采用异步编程模型，可轻松处理高并发请求，尤…...

编程日记 2025/5/4 17:41:40

基于微信小程序的智慧乡村旅游服务平台【附源码】

基于微信小程序的智慧乡村旅游服务平台（源码L文说明文档） 目录 4系统设计 4.1系统功能设计 4.2系统结构 4.3.数据库设计 4.3.1数据库实体 4.3.2数据库设计表 5系统详细实现 5.1 管理员模块的实现 5.1.1旅游景点管理…...

编程日记 2025/5/7 3:19:30

llm-universe 踩坑记录

踩坑云服务器2G不够，因为后面用到内存向量数据库，把数据加载到内存，一个大点的pdf就导致整个服务器崩了。当时可以选择不加载大的文件，自己替换一个小点的pdf 注意点 LLM API.ipynb 这节要注意看下API的含义，了解m…...

编程日记 2025/5/3 23:20:07

【案例】跨境电商企业实践云成本优化，选对平台是关键

某跨境电商企业近年因业务发展迅猛，近年来在全球市场大力拓展业务。然而，伴随其全球化布局的深化，云资源成本逐年攀升，每年在云资源方面的投入超 500万元。庞大的云资源使用量虽支撑了业务的快速发展，但也带来了较高的…...

编程日记 2025/4/29 19:57:54

系统思考与时间管理

时间管理的真正秘诀：主动浪费时间？ 巴菲特的私人飞机驾驶员觉得自己不够成功，于是向巴菲特请教应该怎么做。巴菲特让他列出了自己人生中最想实现的25个目标，并按重要程度排序，接着安排时间专注做前五件最重要的事情。…...

编程日记 2025/4/22 10:03:25

洛谷.P1563 [NOIP 2016 提高组] 玩具谜题

P1563 [NOIP 2016 提高组] 玩具谜题 - 洛谷代码区： #include<algorithm> #include<iostream> #include<cstring> #include<string> #include<vector>using namespace std; const int MAX 1000005; struct PEOPLE {int cx;//0朝内…...

编程日记 2025/5/7 15:22:32