算法总结10 线段树
算法总结10 线段树
- 线段树
- 2569. 更新数组后处理求和查询
线段树
有一个数组,我们要:
- 更新数组的值(例如:都加上一个数,把子数组内的元素取反)
- 查询一个子数组的值(例如:求和,求最大值,求最小值)
更新于查询,如果暴力去做,每个操作都是O(n)的。所以我们需要提升效率。
两大思想:
- 挑选O(n)个特殊区间,使得任意一个区间,可以拆分为O(logn)个特殊区间(用最近公共祖先来思考)
O(n)<=4n
挑选O(n)个特殊区间:build

- lazy 更新 / 延迟更新
lazy tag:用一个数组维护每个区间需要更新的值
如果说这个值 = 0,表示不需要更新
如果这个值 != 0,表示更新操作在这个区间停住了,不继续地柜更新子区间了
如果后面又来了一个更新,破坏了于lazy tag的区间,那么这个区间就得继续递归更新了
模板:
class Solution:def handleQuery(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:n = len(nums1)todo = [0] * (4 * n)def build(o: int, l: int, r: int) -> None:if l == r:# ...returnm = (l + r) // 2build(o * 2, l, m)build(o * 2 + 1, m + 1, r)# 维护...# 更新 [L,R]def update(o: int, l: int, r: int, L: int, R: int, add: int) -> None:if L <= l and r <= R:# 更新 ...todo[o] += add # 不再继续递归更新了return m = (l + r)//2# 需要继续递归,就把 todo[o] 的内容传下去(给左右儿子)if todo[o] != 0:todo[o*2] += todo[o]todo[o*2+1] += todo[o]todo[o] = 0if m >= L:update(o*2, l, m, L, R, add)if m < R:update(o*2+1, m+1, r, L, R, add)# 维护 ...
2569. 更新数组后处理求和查询
2569. 更新数组后处理求和查询
class Solution:def handleQuery(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:n = len(nums1)cnt = [0]*(4*n)todo = [False]*(4*n)# 求非叶子节点def maintain(o):cnt[o] = cnt[o*2] + cnt[o*2+1]# 进行01翻转def do(o, l, r):# 翻转cnt[o] = r-l+1-cnt[o]# 翻一次为反,翻两次为正todo[o] = not todo[o]# 初始化线段树def build(o, l, r):# 叶子结点if l == r:cnt[o] = nums1[l-1]return# 非叶子结点 mid = (l+r)//2build(o*2, l, mid)build(o*2+1, mid+1, r)maintain(o)def update(o, l, r, L, R):if L<=l and r<=R:do(o, l, r)returnmid = (l+r)//2# 先将当前节点的值传给子节点if todo[o]:do(o*2, l, mid)do(o*2+1, mid+1, r)todo[o]=False# 待翻转的区间有分歧,二分处理if mid>=L:update(o*2, l, mid, L, R)if mid<R:update(o*2+1,mid+1, r, L, R)# 反转后更新节点的值maintain(o)# 初始化build(1, 1, n)# 记录答案,求和(每次都是在sum(nums2)的基础上增加值l*cnt[1])ans, s = [], sum(nums2)for op, l, r in queries:if op == 1:# 每次都从整个范围,将l+1和r+1的范围进行翻转(索引从1开始)update(1, 1, n, l+1, r+1)elif op == 2:# cnt从1开始s += l*cnt[1]else:ans.append(s)return ans
参考
相关文章:
算法总结10 线段树
算法总结10 线段树 线段树2569. 更新数组后处理求和查询 线段树 有一个数组,我们要: 更新数组的值(例如:都加上一个数,把子数组内的元素取反)查询一个子数组的值(例如:求和&#x…...
518抽奖软件,支持按人像照片抽奖
518抽奖软件简介 518抽奖软件,518我要发,超好用的年会抽奖软件,简约设计风格。 包含文字号码抽奖、照片抽奖两种模式,支持姓名抽奖、号码抽奖、数字抽奖、照片抽奖。(www.518cj.net) 照片抽奖模式 圆角边框 照片抽奖模式下&am…...
数字IC笔试面试题之--时钟偏斜(skew)与抖动(jitter)
1 时钟偏斜(clock skew) 时钟偏斜(偏移)是因为布线长度和负载不同,导致同一时钟上升沿到不同触发器的时间不同。这一时间差,即为时钟偏移。 时钟偏斜可能导致时序违例(本文直接粘贴了参考博客…...
免费api接口:物流api,企业工商查询api,游戏api。。。
免费api接口,物流api,企业工商查询api,游戏api。。。都有。 Facebook Games Services - Facebook Games Services 为游戏开发者提供了各种服务, 包括(但不限于) 成就 API, 分数 API, 应用通知, 请求, 游戏养成和 Facebook SDK for Unity.Google Play Games Service…...
第二十八章 Classes - 引用其他类的方法
文章目录 第二十八章 Classes - 引用其他类的方法引用其他类的方法对当前实例的引用 第二十八章 Classes - 引用其他类的方法 引用其他类的方法 在方法(或例程)中,使用下面的语法来引用其他类中的方法: 要调用类方法并访问其返回值,请使用如下表达式:…...
Android 中集成 TensorFlow Lite图片识别
在上图通过手机的相机拍摄到的物体识别出具体的名称,这个需要通过TensorFlow 训练的模型引用到项目中;以下就是详细地集成 TensorFlow步骤,请按照以下步骤进行操作: 在项目的根目录下的 build.gradle 文件中添加 TensorFlow 的 Ma…...
NSSCTF之Misc篇刷题记录(16)
NSSCTF之Misc篇刷题记录(16) [黑盾杯 2020]encrypt[UTCTF 2020]Spectre[UTCTF 2020]Observe closely NSSCTF平台:https://www.nssctf.cn/ PS:所有FLAG改为NSSCTF [黑盾杯 2020]encrypt UTAxSlUwTkRWRVo3Um1GclpWOWxibU55ZVhCMGFX…...
域名解析--nslookup和dig
dig (Domain Information Groper) dig 是一个功能强大且更灵活的 DNS 查询工具,通常在 Linux 和 macOS 等 Unix-like 操作系统上使用。以下是 dig 的一些常见用法和区别: 查询域名信息 dig example.com这将返回与指定域名相关的 DNS 记录,…...
EXCEL如何把一个单元格内的文本和数字分开?例如:龚龚15565 = 龚龚 15565
使用工具:WPS 举例: EXCEL如何把一个单元格内的文本和数字批量分开?不使用数据分列。 第一步、将第二行数据冻结 第二步、在B1、C1单元格输入需要分开的示例 第三步、点击选中B1单元格,输入快捷键【CTRLE】进行填充。B2单元格也是…...
uniapp抽取组件绑定事件中箭头函数含花括号无法解析
版本: "dcloudio/uni-ui": "^1.4.27", "vue": "> 2.6.14 < 2.7"... 箭头函数后含有花括号的时候, getData就拿不到val参数 , 解决办法就是去除花括号 // 错误代码: <SearchComp change"(val) > { getData({ val …...
猫头虎博主第四期赠书活动:《精通Go语言:(第2版) 》
🌷🍁 博主猫头虎(🐅🐾)带您 Go to New World✨🍁 🦄 博客首页——🐅🐾猫头虎的博客🎐 🐳 《面试题大全专栏》 🦕 文章图文…...
【学习总结】EasyExcel合并同列不同行,表格数据相同的行
实体类 Data HeadRowHeight(50) ContentStyle(horizontalAlignment HorizontalAlignmentEnum.CENTER, verticalAlignment VerticalAlignmentEnum.CENTER, wrapped BooleanEnum.TRUE) public class CriterionDataExportDTO {ColumnWidth(15)ExcelProperty(value "所属…...
Tokenview X-ray功能:深入探索EVM系列浏览器的全新视角
Tokenview作为一家领先的多链区块浏览器,为了进一步优化区块链用户的使用体验,我们推出了X-ray(余额透视)功能。该功能将帮助您深入了解EVM系列浏览器上每个地址的交易过程,以一种直观、简洁的方式呈现地址的进出账情况…...
【洛谷 P1364】医院设置 题解(图论+深度优先搜索)
医院设置 题目描述 设有一棵二叉树,如图: 其中,圈中的数字表示结点中居民的人口。圈边上数字表示结点编号,现在要求在某个结点上建立一个医院,使所有居民所走的路程之和为最小,同时约定,相邻接…...
【Java基础】- RMI原理和使用详解
【Java基础】- RMI原理和使用详解 文章目录 【Java基础】- RMI原理和使用详解一、什么RMI二、RMI原理2.1 工作原理图2.2 工作原理 三、RMI远程调用步骤3.1 RMI远程调用运行流程图3.2 RMI 远程调用步骤 四、JAVA RMI简单实现4.1 如何实现一个RMI程序4.2 JAVA实现RMI程序 一、什么…...
无水印免费4K视频素材网站 可商用-Free Stock Video
Free Stock Video是一个在线无水印免费4K视频素材网站,提供各种类型的4k、1080p的视频素材共免费下载,包括美食、水、自然、冬季、无人机、云朵、慢动作、夕阳、动态背景、缩时摄影、旅游和烟火,也可通过关键词搜索方式找到相关视频素材内容&…...
kubesphere中间件部署
微服务部署前中间件部署 一、MySQL部署 1.1 使用Docker实现MySQL主从复制 docker run -p 3307:3306 --name mysql-master \ -v /mydata/mysql/master/log:/var/log/mysql \ -v /mydata/mysql/master/data:/var/lib/mysql \ -v /mydata/mysql/master/conf:/etc/mysql \ -e My…...
使用 AWS S3 SDK 访问 COS-腾讯云国际站代充
腾讯云国际站对象存储(Cloud Object Storage,COS)提供了 AWS S3 兼容的 API,因此当用户的数据从 S3 迁移到 COS 之后,只需要进行简单的配置修改,即可让客户端应用轻松兼容 COS 服务。下面unirech小编主要介…...
c语言每日一练(15)
前言:每日一练系列,每一期都包含5道选择题,2道编程题,博主会尽可能详细地进行讲解,令初学者也能听的清晰。每日一练系列会持续更新,上学期间将看学业情况更新。 五道选择题: 1、程序运行的结果…...
如何利用软文推广进行SEO优化(打造优质软文,提升网站排名)
在当今的互联网时代,SEO优化成为了网站推广的关键。而软文推广作为一种有效的推广方式,其优点不仅仅局限于SEO,还可以带来更多的曝光和用户流量。本文将深入探讨如何做好软文推广,从而提升网站排名和流量。 了解目标受众群体 内容…...
Flask RESTful 示例
目录 1. 环境准备2. 安装依赖3. 修改main.py4. 运行应用5. API使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题: 下面创建一个简单的Flask RESTful API示例。首先,我们需要创建环境,安装必要的依赖,然后…...
在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能
下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能,包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...
8k长序列建模,蛋白质语言模型Prot42仅利用目标蛋白序列即可生成高亲和力结合剂
蛋白质结合剂(如抗体、抑制肽)在疾病诊断、成像分析及靶向药物递送等关键场景中发挥着不可替代的作用。传统上,高特异性蛋白质结合剂的开发高度依赖噬菌体展示、定向进化等实验技术,但这类方法普遍面临资源消耗巨大、研发周期冗长…...
【SpringBoot】100、SpringBoot中使用自定义注解+AOP实现参数自动解密
在实际项目中,用户注册、登录、修改密码等操作,都涉及到参数传输安全问题。所以我们需要在前端对账户、密码等敏感信息加密传输,在后端接收到数据后能自动解密。 1、引入依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId...
LeetCode - 394. 字符串解码
题目 394. 字符串解码 - 力扣(LeetCode) 思路 使用两个栈:一个存储重复次数,一个存储字符串 遍历输入字符串: 数字处理:遇到数字时,累积计算重复次数左括号处理:保存当前状态&a…...
高等数学(下)题型笔记(八)空间解析几何与向量代数
目录 0 前言 1 向量的点乘 1.1 基本公式 1.2 例题 2 向量的叉乘 2.1 基础知识 2.2 例题 3 空间平面方程 3.1 基础知识 3.2 例题 4 空间直线方程 4.1 基础知识 4.2 例题 5 旋转曲面及其方程 5.1 基础知识 5.2 例题 6 空间曲面的法线与切平面 6.1 基础知识 6.2…...
【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具
第2章 虚拟机性能监控,故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令:jps [options] [hostid] 功能:本地虚拟机进程显示进程ID(与ps相同),可同时显示主类&#x…...
算法笔记2
1.字符串拼接最好用StringBuilder,不用String 2.创建List<>类型的数组并创建内存 List arr[] new ArrayList[26]; Arrays.setAll(arr, i -> new ArrayList<>()); 3.去掉首尾空格...
保姆级教程:在无网络无显卡的Windows电脑的vscode本地部署deepseek
文章目录 1 前言2 部署流程2.1 准备工作2.2 Ollama2.2.1 使用有网络的电脑下载Ollama2.2.2 安装Ollama(有网络的电脑)2.2.3 安装Ollama(无网络的电脑)2.2.4 安装验证2.2.5 修改大模型安装位置2.2.6 下载Deepseek模型 2.3 将deepse…...
uniapp手机号一键登录保姆级教程(包含前端和后端)
目录 前置条件创建uniapp项目并关联uniClound云空间开启一键登录模块并开通一键登录服务编写云函数并上传部署获取手机号流程(第一种) 前端直接调用云函数获取手机号(第三种)后台调用云函数获取手机号 错误码常见问题 前置条件 手机安装有sim卡手机开启…...
