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

算法总结10 线段树

算法总结10 线段树

  • 线段树
  • 2569. 更新数组后处理求和查询

线段树

有一个数组,我们要:

  1. 更新数组的值(例如:都加上一个数,把子数组内的元素取反)
  2. 查询一个子数组的值(例如:求和,求最大值,求最小值)

更新于查询,如果暴力去做,每个操作都是O(n)的。所以我们需要提升效率。

两大思想:

  1. 挑选O(n)个特殊区间,使得任意一个区间,可以拆分为O(logn)个特殊区间(用最近公共祖先来思考)
    O(n)<=4n

挑选O(n)个特殊区间:build

在这里插入图片描述

  1. 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. 更新数组后处理求和查询 线段树 有一个数组&#xff0c;我们要&#xff1a; 更新数组的值&#xff08;例如&#xff1a;都加上一个数&#xff0c;把子数组内的元素取反&#xff09;查询一个子数组的值&#xff08;例如&#xff1a;求和&#x…...

518抽奖软件,支持按人像照片抽奖

518抽奖软件简介 518抽奖软件&#xff0c;518我要发&#xff0c;超好用的年会抽奖软件&#xff0c;简约设计风格。 包含文字号码抽奖、照片抽奖两种模式&#xff0c;支持姓名抽奖、号码抽奖、数字抽奖、照片抽奖。(www.518cj.net) 照片抽奖模式 圆角边框 照片抽奖模式下&am…...

数字IC笔试面试题之--时钟偏斜(skew)与抖动(jitter)

1 时钟偏斜&#xff08;clock skew&#xff09; 时钟偏斜&#xff08;偏移&#xff09;是因为布线长度和负载不同&#xff0c;导致同一时钟上升沿到不同触发器的时间不同。这一时间差&#xff0c;即为时钟偏移。 时钟偏斜可能导致时序违例&#xff08;本文直接粘贴了参考博客…...

免费api接口:物流api,企业工商查询api,游戏api。。。

免费api接口&#xff0c;物流api,企业工商查询api,游戏api。。。都有。 Facebook Games Services - Facebook Games Services 为游戏开发者提供了各种服务, 包括(但不限于) 成就 API, 分数 API, 应用通知, 请求, 游戏养成和 Facebook SDK for Unity.Google Play Games Service…...

第二十八章 Classes - 引用其他类的方法

文章目录 第二十八章 Classes - 引用其他类的方法引用其他类的方法对当前实例的引用 第二十八章 Classes - 引用其他类的方法 引用其他类的方法 在方法(或例程)中&#xff0c;使用下面的语法来引用其他类中的方法: 要调用类方法并访问其返回值&#xff0c;请使用如下表达式:…...

Android 中集成 TensorFlow Lite图片识别

在上图通过手机的相机拍摄到的物体识别出具体的名称&#xff0c;这个需要通过TensorFlow 训练的模型引用到项目中&#xff1b;以下就是详细地集成 TensorFlow步骤&#xff0c;请按照以下步骤进行操作&#xff1a; 在项目的根目录下的 build.gradle 文件中添加 TensorFlow 的 Ma…...

NSSCTF之Misc篇刷题记录(16)

NSSCTF之Misc篇刷题记录&#xff08;16&#xff09; [黑盾杯 2020]encrypt[UTCTF 2020]Spectre[UTCTF 2020]Observe closely NSSCTF平台&#xff1a;https://www.nssctf.cn/ PS&#xff1a;所有FLAG改为NSSCTF [黑盾杯 2020]encrypt UTAxSlUwTkRWRVo3Um1GclpWOWxibU55ZVhCMGFX…...

域名解析--nslookup和dig

dig (Domain Information Groper) dig 是一个功能强大且更灵活的 DNS 查询工具&#xff0c;通常在 Linux 和 macOS 等 Unix-like 操作系统上使用。以下是 dig 的一些常见用法和区别&#xff1a; 查询域名信息 dig example.com这将返回与指定域名相关的 DNS 记录&#xff0c;…...

EXCEL如何把一个单元格内的文本和数字分开?例如:龚龚15565 = 龚龚 15565

使用工具&#xff1a;WPS 举例&#xff1a; EXCEL如何把一个单元格内的文本和数字批量分开&#xff1f;不使用数据分列。 第一步、将第二行数据冻结 第二步、在B1、C1单元格输入需要分开的示例 第三步、点击选中B1单元格&#xff0c;输入快捷键【CTRLE】进行填充。B2单元格也是…...

uniapp抽取组件绑定事件中箭头函数含花括号无法解析

版本: "dcloudio/uni-ui": "^1.4.27", "vue": "> 2.6.14 < 2.7"... 箭头函数后含有花括号的时候, getData就拿不到val参数 , 解决办法就是去除花括号 // 错误代码: <SearchComp change"(val) > { getData({ val …...

猫头虎博主第四期赠书活动:《精通Go语言:(第2版) 》

&#x1f337;&#x1f341; 博主猫头虎&#xff08;&#x1f405;&#x1f43e;&#xff09;带您 Go to New World✨&#x1f341; &#x1f984; 博客首页——&#x1f405;&#x1f43e;猫头虎的博客&#x1f390; &#x1f433; 《面试题大全专栏》 &#x1f995; 文章图文…...

【学习总结】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作为一家领先的多链区块浏览器&#xff0c;为了进一步优化区块链用户的使用体验&#xff0c;我们推出了X-ray&#xff08;余额透视&#xff09;功能。该功能将帮助您深入了解EVM系列浏览器上每个地址的交易过程&#xff0c;以一种直观、简洁的方式呈现地址的进出账情况…...

【洛谷 P1364】医院设置 题解(图论+深度优先搜索)

医院设置 题目描述 设有一棵二叉树&#xff0c;如图&#xff1a; 其中&#xff0c;圈中的数字表示结点中居民的人口。圈边上数字表示结点编号&#xff0c;现在要求在某个结点上建立一个医院&#xff0c;使所有居民所走的路程之和为最小&#xff0c;同时约定&#xff0c;相邻接…...

【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视频素材网站&#xff0c;提供各种类型的4k、1080p的视频素材共免费下载&#xff0c;包括美食、水、自然、冬季、无人机、云朵、慢动作、夕阳、动态背景、缩时摄影、旅游和烟火&#xff0c;也可通过关键词搜索方式找到相关视频素材内容&…...

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-腾讯云国际站代充

腾讯云国际站对象存储&#xff08;Cloud Object Storage&#xff0c;COS&#xff09;提供了 AWS S3 兼容的 API&#xff0c;因此当用户的数据从 S3 迁移到 COS 之后&#xff0c;只需要进行简单的配置修改&#xff0c;即可让客户端应用轻松兼容 COS 服务。下面unirech小编主要介…...

c语言每日一练(15)

前言&#xff1a;每日一练系列&#xff0c;每一期都包含5道选择题&#xff0c;2道编程题&#xff0c;博主会尽可能详细地进行讲解&#xff0c;令初学者也能听的清晰。每日一练系列会持续更新&#xff0c;上学期间将看学业情况更新。 五道选择题&#xff1a; 1、程序运行的结果…...

如何利用软文推广进行SEO优化(打造优质软文,提升网站排名)

在当今的互联网时代&#xff0c;SEO优化成为了网站推广的关键。而软文推广作为一种有效的推广方式&#xff0c;其优点不仅仅局限于SEO&#xff0c;还可以带来更多的曝光和用户流量。本文将深入探讨如何做好软文推广&#xff0c;从而提升网站排名和流量。 了解目标受众群体 内容…...

TDengine 快速体验(Docker 镜像方式)

简介 TDengine 可以通过安装包、Docker 镜像 及云服务快速体验 TDengine 的功能&#xff0c;本节首先介绍如何通过 Docker 快速体验 TDengine&#xff0c;然后介绍如何在 Docker 环境下体验 TDengine 的写入和查询功能。如果你不熟悉 Docker&#xff0c;请使用 安装包的方式快…...

安宝特方案丨XRSOP人员作业标准化管理平台:AR智慧点检验收套件

在选煤厂、化工厂、钢铁厂等过程生产型企业&#xff0c;其生产设备的运行效率和非计划停机对工业制造效益有较大影响。 随着企业自动化和智能化建设的推进&#xff0c;需提前预防假检、错检、漏检&#xff0c;推动智慧生产运维系统数据的流动和现场赋能应用。同时&#xff0c;…...

dedecms 织梦自定义表单留言增加ajax验证码功能

增加ajax功能模块&#xff0c;用户不点击提交按钮&#xff0c;只要输入框失去焦点&#xff0c;就会提前提示验证码是否正确。 一&#xff0c;模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...

pikachu靶场通关笔记22-1 SQL注入05-1-insert注入(报错法)

目录 一、SQL注入 二、insert注入 三、报错型注入 四、updatexml函数 五、源码审计 六、insert渗透实战 1、渗透准备 2、获取数据库名database 3、获取表名table 4、获取列名column 5、获取字段 本系列为通过《pikachu靶场通关笔记》的SQL注入关卡(共10关&#xff0…...

Maven 概述、安装、配置、仓库、私服详解

目录 1、Maven 概述 1.1 Maven 的定义 1.2 Maven 解决的问题 1.3 Maven 的核心特性与优势 2、Maven 安装 2.1 下载 Maven 2.2 安装配置 Maven 2.3 测试安装 2.4 修改 Maven 本地仓库的默认路径 3、Maven 配置 3.1 配置本地仓库 3.2 配置 JDK 3.3 IDEA 配置本地 Ma…...

LINUX 69 FTP 客服管理系统 man 5 /etc/vsftpd/vsftpd.conf

FTP 客服管理系统 实现kefu123登录&#xff0c;不允许匿名访问&#xff0c;kefu只能访问/data/kefu目录&#xff0c;不能查看其他目录 创建账号密码 useradd kefu echo 123|passwd -stdin kefu [rootcode caozx26420]# echo 123|passwd --stdin kefu 更改用户 kefu 的密码…...

【Go语言基础【12】】指针:声明、取地址、解引用

文章目录 零、概述&#xff1a;指针 vs. 引用&#xff08;类比其他语言&#xff09;一、指针基础概念二、指针声明与初始化三、指针操作符1. &&#xff1a;取地址&#xff08;拿到内存地址&#xff09;2. *&#xff1a;解引用&#xff08;拿到值&#xff09; 四、空指针&am…...

抽象类和接口(全)

一、抽象类 1.概念&#xff1a;如果⼀个类中没有包含⾜够的信息来描绘⼀个具体的对象&#xff0c;这样的类就是抽象类。 像是没有实际⼯作的⽅法,我们可以把它设计成⼀个抽象⽅法&#xff0c;包含抽象⽅法的类我们称为抽象类。 2.语法 在Java中&#xff0c;⼀个类如果被 abs…...

【Linux手册】探秘系统世界:从用户交互到硬件底层的全链路工作之旅

目录 前言 操作系统与驱动程序 是什么&#xff0c;为什么 怎么做 system call 用户操作接口 总结 前言 日常生活中&#xff0c;我们在使用电子设备时&#xff0c;我们所输入执行的每一条指令最终大多都会作用到硬件上&#xff0c;比如下载一款软件最终会下载到硬盘上&am…...

VisualXML全新升级 | 新增数据库编辑功能

VisualXML是一个功能强大的网络总线设计工具&#xff0c;专注于简化汽车电子系统中复杂的网络数据设计操作。它支持多种主流总线网络格式的数据编辑&#xff08;如DBC、LDF、ARXML、HEX等&#xff09;&#xff0c;并能够基于Excel表格的方式生成和转换多种数据库文件。由此&…...