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

【leetcode难题】2569. 更新数组后处理求和查询【线段树实现01翻转和区间求和模版】

题目截图

在这里插入图片描述

题目分析

  • 关键就是记录每次操作2时,nums1中的1的个数
  • 这就需要实现线段树进行区间反转以及区间求和

ac code

class Solution:def handleQuery(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:n = len(nums1)m = len(queries)seg_tree = SegTree(nums1)# 只需要记录每次2操作时nums1中有多少个1即可total = sum(nums2)ans = []for i in range(m):if queries[i][0] == 1:l = queries[i][1]r = queries[i][2]seg_tree.reverse_range(l, r)elif queries[i][0] == 2:total += seg_tree.sum_range(0, n - 1) * queries[i][1]elif queries[i][0] == 3:ans.append(total)return ansclass SegTree:def __init__(self, nums):n = len(nums)self.arr = [SegNode() for _ in range(n * 4 + 1)]self.build(1, 0, n - 1, nums)def sum_range(self, left, right):return self.query(1, left, right)def reverse_range(self, left, right):self.modify(1, left, right)def build(self, id, l, r, nums):arr = self.arrarr[id] = SegNode()arr[id].l = larr[id].r = rarr[id].lazytag = Falseif l == r:arr[id].sum = nums[l]returnmid = (l + r) >> 1self.build(2 * id, l, mid, nums)self.build(2 * id + 1, mid + 1, r, nums)arr[id].sum = arr[2 * id].sum + arr[2 * id + 1].sum# pushdown函数:下传懒标记,即将当前区间的修改情况下传到其左右孩子结点def pushdown(self, x):arr = self.arrif arr[x].lazytag:arr[2 * x].lazytag = not arr[2 * x].lazytagarr[2 * x].sum = arr[2 * x].r - arr[2 * x].l + 1 - arr[2 * x].sumarr[2 * x + 1].lazytag = not arr[2 * x + 1].lazytagarr[2 * x + 1].sum = arr[2 * x + 1].r - arr[2 * x + 1].l + 1 - arr[2 * x + 1].sumarr[x].lazytag = False# 区间修改def modify(self, id, l, r):arr = self.arrif arr[id].l >= l and arr[id].r <= r:arr[id].sum = (arr[id].r - arr[id].l + 1) - arr[id].sumarr[id].lazytag = not arr[id].lazytagreturnself.pushdown(id)mid = (arr[id].l + arr[id].r) >> 1if arr[2 * id].r >= l:self.modify(2 * id, l, r)if arr[2 * id + 1].l <= r:self.modify(2 * id + 1, l, r)arr[id].sum = arr[2 * id].sum + arr[2 * id + 1].sum# 区间查询def query(self, id, l, r):arr = self.arrif arr[id].l >= l and arr[id].r <= r:return arr[id].sumif arr[id].r < l or arr[id].l > r:return 0self.pushdown(id)mid = (arr[id].l + arr[id].r) >> 1res = 0if arr[2 * id].r >= l:res += self.query(2 * id, l, r)if arr[2 * id + 1].l <= r:res += self.query(2 * id + 1, l, r)return resclass SegNode:def __init__(self):self.l = 0self.r = 0self.sum = 0self.lazytag = False

相关文章:

【leetcode难题】2569. 更新数组后处理求和查询【线段树实现01翻转和区间求和模版】

题目截图 题目分析 关键就是记录每次操作2时&#xff0c;nums1中的1的个数这就需要实现线段树进行区间反转以及区间求和 ac code class Solution:def handleQuery(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:n len(nums1)m le…...

练习时长两年半的入侵检测

计算机安全的三大中心目标是&#xff1a;保密性 (Conf idential ity) 、完整性 (Integrity) 、可用性 (Availability) 。 身份认证与识别、访问控制机制、加密技术、防火墙技术等技术共同特征就是集中在系统的自身加固和防护上&#xff0c;属于静态的安全防御技术&#xff0c;…...

【弹力设计篇】聊聊隔离设计

为什么需要隔离设计 隔离其实就是Bulkheads&#xff0c;隔板。在生活中隔板的应用主要在船舱中进行设计&#xff0c;目的是为了避免因一处漏水导致整个船都沉下去。可以将故障减少在一定的范围内&#xff0c;而不是整个船体。 从架构演变来说的话&#xff0c;大多数系统都是从…...

MFC 透明窗体

如何制作透明窗体 &#xff1f;&#xff1f;&#xff1f;&#xff1f;&#xff1f; 使用SetLayeredWindowAttributes可以方便的制作透明窗体&#xff0c;此函数在w2k以上才支持,而且如果希望直接使用的话&#xff0c;可能需要下载最新的SDK。不过此函数在w2k的user32.dll里有实…...

C++笔记之vector的resize()和clear()用法

C笔记之vector的resize()和clear()用法 code review! 文章目录 C笔记之vector的resize()和clear()用法1.resize()2.clear() 1.resize() 运行 2.clear() 运行...

Vue2基础九、路由

零、文章目录 Vue2基础九、路由 1、单页应用 &#xff08;1&#xff09;单页应用是什么 单页面应用(SPA&#xff1a;Single Page Application): 所有功能在 一个html页面 上实现具体示例: 网易云音乐 https://music.163.com/ &#xff08;2&#xff09;单页面应用VS多页面…...

移动零——力扣283

题目描述 双指针 class Solution{ public:void moveZeroes(vector<int>& nums){int n nums.size(), left0, right0;while(right<n){if(nums[right]){swap(nums[right], nums[left]);left;}right;}} };...

Transformer+MIA Future Work

TransformerMIA Future Work 主要的挑战和未来发展分为三个部分&#xff0c;即 1、特征集成和计算成本降低、 2、数据增强和数据集收集、 3、学习方式和模态-对象分布 1、特征集成和计算成本降低 为了同时捕获局部和全局特征来提高模型性能&#xff0c;目前大多数工作只是…...

深度学习入门(二):神经网络整体架构

一、前向传播 作用于每一层的输入&#xff0c;通过逐层计算得到输出结果 二、反向传播 作用于网络输出&#xff0c;通过计算梯度由深到浅更新网络参数 三、整体架构 层次结构&#xff1a;逐层变换数据 神经元&#xff1a;数据量、矩阵大小&#xff08;代表输入特征的数量…...

rust 配置

rustup 镜像 在 cmd 中输入以下代码&#xff0c;设置环境变量 setx RUSTUP_UPDATE_ROOT https://mirrors.tuna.tsinghua.edu.cn/rustup/rustup setx RUSTUP_DIST_SERVER https://mirrors.tuna.tsinghua.edu.cn/rustupcrates.io 索引镜像 在 C:\Users\用户名\.cargo\config 文…...

文心一言 VS 讯飞星火 VS chatgpt (67)-- 算法导论6.5 6题

文心一言 VS 讯飞星火 VS chatgpt &#xff08;67&#xff09;-- 算法导论6.5 6题 六、在 HEAP-INCREASE-KEY 的第 5 行的交换操作中&#xff0c;一般需要通过三次赋值来完成。想一想如何利用INSERTION-SORT 内循环部分的思想&#xff0c;只用一次赋值就完成这一交换操作? 文…...

6、Kubernetes核心技术 - Pod

目录 一、概述 二、Pod机制 2.1、共享网络 2.2、共享存储 三、Pod资源清单 四、 Pod 的分类 五、Pod阶段 六、Pod 镜像拉取策略 ImagePullBackOff 七、Pod 资源限制 八、容器重启策略 一、概述 Pod 是可以在 Kubernetes 中创建和管理的、最小的可部署的计算单元。P…...

VlanIf虚拟接口 通信技术(二十三课)

一 Vlan技术之间的通信 单臂路由(One-Arm Routing)是一种网络架构设计方式,通常用于部署网络设备(如防火墙、负载均衡器等)实现网络流量控制和安全策略。在单臂路由中,网络设备只有一个物理接口与局域网(LAN)或广域网(WAN)相连。 1.2 交换机 数据链路层 (第二层)…...

图神经网络(GNN)入门学习笔记(直观且简单)

文章目录 图的定义和表示可以使用图数据结构的问题将图结构用于机器学习的挑战最基本的图神经网络概述汇聚操作基于信息传递的改进图神经网络全局向量信息的利用 本篇文章参考发表于Distill上的图神经网络入门博客&#xff1a; A Gentle Introduction to Graph Neural Network…...

【Java开发】 Mybatis-Flex 01:快速入门

Mybatis 作为头部的 ORM 框架&#xff0c;他的增强工具可谓层出不穷&#xff0c;比如出名的 Mybatis-Plus 和 阿里云开源的 Fluent-MyBatis&#xff0c;如今出了一款 Mybatis-Flex &#xff0c;相比前两款功能更为强大、性能更为强悍&#xff0c;不妨来了解一下。 目录 1 Myba…...

企业级业务架构学习笔记<二>

一.业务架构基础 业务架构的定义 以实现企业战略为目标&#xff0c;构建企业整体业务能力规划并将其传导给技术实现端的结构化企业能力分析方法 (业务架构可以从企业战略触发&#xff0c;按照企业战略设计业务及业务过程&#xff0c;业务过程时需要业务能力支撑的&#xff0…...

Minio在windows环境配置https访问

minio启动后&#xff0c;默认访问方式为http&#xff0c;但是有的时候我们的访问场景必须是https&#xff0c;浏览器有的会默认以https进行访问&#xff0c;这个时候就需要我们进行配置上的调整&#xff0c;将minio从http访问升级到https。而查看minio的官方文档&#xff0c;并…...

安装JDK环境(Windows+Linux双教程)

今日一语&#xff1a;今天的事情不去做&#xff0c;到了明天就成了麻烦&#xff0c;到了下个月就成了隐患&#xff0c;到了明年只剩下悔恨和惋惜 Linux 从Oracle网站下载linux的rpm包java -version 查询java环境是否已经安装 如果已经安装&#xff0c;可以选择卸载重装或者直接…...

SVG图标,SVG symbols,SVG use标签

SVG图标&#xff0c;SVG symbols 项目中图标的使用&#xff0c;趋势是使用svg作图标的&#xff0c;优点如下 兼容现有图片能力前提还支持矢量 可读性好&#xff0c;有利于SEO与无障碍 在性能和维护性方面也比iconfont要强很多 怎么在项目中优雅的使用svg图标&#xff0c;下面…...

常用css 笔记

0、定义变量 :root { --primary-color: #007bff;} .button { background-color: var(--primary-color);} 1、水平垂直居中 div {width: 100px;height: 100px;position: absolute;top: 0;right: 0;bottom: 0;left: 0;margin: auto; }父级控制子集居中 .parent {display: fle…...

谷歌浏览器插件

项目中有时候会用到插件 sync-cookie-extension1.0.0&#xff1a;开发环境同步测试 cookie 至 localhost&#xff0c;便于本地请求服务携带 cookie 参考地址&#xff1a;https://juejin.cn/post/7139354571712757767 里面有源码下载下来&#xff0c;加在到扩展即可使用FeHelp…...

【JVM】- 内存结构

引言 JVM&#xff1a;Java Virtual Machine 定义&#xff1a;Java虚拟机&#xff0c;Java二进制字节码的运行环境好处&#xff1a; 一次编写&#xff0c;到处运行自动内存管理&#xff0c;垃圾回收的功能数组下标越界检查&#xff08;会抛异常&#xff0c;不会覆盖到其他代码…...

【磁盘】每天掌握一个Linux命令 - iostat

目录 【磁盘】每天掌握一个Linux命令 - iostat工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景 注意事项 【磁盘】每天掌握一个Linux命令 - iostat 工具概述 iostat&#xff08;I/O Statistics&#xff09;是Linux系统下用于监视系统输入输出设备和CPU使…...

[10-3]软件I2C读写MPU6050 江协科技学习笔记(16个知识点)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16...

数据链路层的主要功能是什么

数据链路层&#xff08;OSI模型第2层&#xff09;的核心功能是在相邻网络节点&#xff08;如交换机、主机&#xff09;间提供可靠的数据帧传输服务&#xff0c;主要职责包括&#xff1a; &#x1f511; 核心功能详解&#xff1a; 帧封装与解封装 封装&#xff1a; 将网络层下发…...

JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作

一、上下文切换 即使单核CPU也可以进行多线程执行代码&#xff0c;CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短&#xff0c;所以CPU会不断地切换线程执行&#xff0c;从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...

DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”

目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...

今日学习:Spring线程池|并发修改异常|链路丢失|登录续期|VIP过期策略|数值类缓存

文章目录 优雅版线程池ThreadPoolTaskExecutor和ThreadPoolTaskExecutor的装饰器并发修改异常并发修改异常简介实现机制设计原因及意义 使用线程池造成的链路丢失问题线程池导致的链路丢失问题发生原因 常见解决方法更好的解决方法设计精妙之处 登录续期登录续期常见实现方式特…...

大语言模型(LLM)中的KV缓存压缩与动态稀疏注意力机制设计

随着大语言模型&#xff08;LLM&#xff09;参数规模的增长&#xff0c;推理阶段的内存占用和计算复杂度成为核心挑战。传统注意力机制的计算复杂度随序列长度呈二次方增长&#xff0c;而KV缓存的内存消耗可能高达数十GB&#xff08;例如Llama2-7B处理100K token时需50GB内存&a…...

JavaScript 数据类型详解

JavaScript 数据类型详解 JavaScript 数据类型分为 原始类型&#xff08;Primitive&#xff09; 和 对象类型&#xff08;Object&#xff09; 两大类&#xff0c;共 8 种&#xff08;ES11&#xff09;&#xff1a; 一、原始类型&#xff08;7种&#xff09; 1. undefined 定…...