树状数组(高级数据结构)-蓝桥杯

news/2024/3/29 14:40:54/文章来源:https://blog.csdn.net/weixin_62808713/article/details/129074360

一、简介

  • 树状数组 (Binary Indexed Tree,BIT),利用数的二进制特征进行检索的一种树状结构。

  • 一种真正的高级数据结构: 二分思想、二叉树、位运算、前缀和。

  • 高效!

  • 代码极其简洁!

二、基本应用

  • 数列a1,a2,....,an,操作:

  • 单点修改:修改元素add(k,x): 把ak加上x。

  • 求和:

sum (x) = a1 + ... + ax

区间和ai + ... + aj = sum(j) - sum(i-1)

三、不修改、只查询

  • 数列aj, a2,..., an,求区间和: ai+ ...+aj

  • 数列是静态的,用前缀和计算区间和,特别高效。

  • 前缀和:sum[i]=a1+...+ ai

  • 区间和: ai+...+aj = sum[j]-sum[i-1]

  • 查询一次区间和,O(1)

  • 代码

  • 如果数列是动态的

  • 修改元素add(k,x):把a加上x。

复杂度O(1)

  • 求区间和:sum(j) - sum(i-1)

复杂度:O(n)--------->效率低

四、动态修改、求区间和: 用树状数组

  • 数列是动态的

  • 修改元素add(k,x):把ak加上x。

  • 求区间和:sum(j) - sum(i-1)

  • 复杂度都是: O(logn)

  • 代码

五、从二叉树到树状数组

六、神奇的lowbit(x)操作

  • 语法:lowbit(x)=x &-x

  • 功能:找到x的二进制数的最后一个1

七、tree[ ]数组

  • 从lowbit(x)推出tree[ ]数组,所有的计算都基于tree[ ],令m =lowbit(x)。

  • 定义tree[x]:把ax和它前面共m个数相加。

  • 例: lowbit(6)=2,有tree[6] = a5+a6。

  • 横线中的黑色表示tree[x],等于横线上元素相加的和。

八、基于tree[ ]的计算

  • 求和sum=a1 +...+ax

利用tree[ ]数组求sum,例如:

sum[8] = tree[8]

sum[7] = tree[7] + tree[6] + tree[4]

sum[9] = tree[9] + tree[8]

  • 以上关系是如何得到的?借助lowbit(x)。

九、sum[ ]的计算

  • 例: sum[7] = tree[7] + tree[6] + tree[4]

(1)从7开始,加上tree[7];

(2) 7 -lowbit(7)= 6,加上tree[6];

(3) 6 - lowbit(6) = 4,加上tree[4];

(4) 4-lowbit(4)= 0,结束。

  • sum()的复杂度?--------->O(logn)------非常好!

十、sum[ ]的更新

  • 更改ax,和它相关的tree都会变化。

  • 例如改变a3,那么tree[3]、tree[4]、tree[8]...都会改变。

  • 影响哪些tree[ ]? 仍然利用lowbit(x)

(1) 更改tree[3];

(2) 3 +lowbit(3)= 4,更改tree[4];

(3) 4 +lowbit(4)=8,更改tree[8];

(4)直到最后的tree[n]。

  • 复杂度?--------->O(logn)------非常好!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_71795.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

详解HashMap

目录 1.hash code 2.数据结构 3.初始化 4.存取 4.1.put 4.2.get 5.迭代 6.扩容 7.JDK1.7版本存在的问题 7.1.性能跌落 7.2.循环链表 8.散列运算 9.扰动函数 1.hash code hash code是使用hash函数运算得到的一个值,是对象的身份证号码,用于…

OpenSumi 是信创开发云的首选

原文作者:行云创新技术总监 邓冰寒 引言 随着云原生应用的日益普及,开发上云也逐步被越来越多的厂商和开发者接受,在这个赛道国内外有不少玩家,国外的 GitHub Codespaces、CodeSandbox,GitPod、亚马逊 Cloud9&#xf…

借力英特尔® Smart Edge,灵雀云 ACP 5G 专网解决方案获得多维度优化加速

近日,灵雀云联合英特尔推出了集成Smart Edge 模块的灵雀云 ACP 5G 专网解决方案,同时共同发布了《借力英特尔 Smart Edge,基于云原生解决方案的灵雀云 ACP 5G 专网版本获得多维度优化加速》白皮书。 得益于云计算技术和 5G 网络的高速发展&am…

Win10 环境 安卓ollvm编译与配置 ndk代码混淆加密

确定你正在使用的ndk版本 查看build.gradle ndkVersion 21.4.7075529 确定你使用的ndk的ollvm版本 C:\Users\Administrator\AppData\Local\Android\Sdk\ndk\21.4.7075529\toolchains\llvm\prebuilt\windows-x86_64\bin\llvm-config.exe --version 9.0.9svn 确定了ollvm版本后…

动手学深度学习(第二版)学习笔记 第二章

官网:http://zh.d2l.ai/ 视频可以去b站找 记录的是个人觉得不太熟的知识 第二章 预备知识 代码地址:d2l-zh/pytorch/chapter_preliminaries 2.1 数据操作 2.1. 数据操作 — 动手学深度学习 2.0.0 documentation 如果只想知道张量中元素的总数&#…

GIT分支管理策略

git基本操作git操作的前提条件:本地windows安装git学习idea中的插件使用idea的git基本操作:远程仓库remote更新fetch:git fetch拉取pull: git pull上传push: git push合并merge: git merge 合并分支本地提交commit:git commit分支branch: git branch 查看分支或者 切换分支上述…

软件设计(十四)-UML建模(上)

软件设计(十三)-原码、反码、补码、移码https://blog.csdn.net/ke1ying/article/details/129115844?spm1001.2014.3001.5501 UML建模包含:用例图,类图与对象图,顺序图,活动图,状态图&#xff…

web网页如何实现响应式导航栏--移动端导航栏

背景: 一提到响应式导航栏,大家第一反应可能就是bootstrap响应式导航栏,这个响应式的一般是针对屏幕变小时,视口出现导航栏,可是,展示到移动端的时候,并没有变化??&#…

京东测试进阶之路:初入测试碎碎念篇

1、基本的测试用例设计方法 基本的测试用例设计方法(边界值分析、等价类划分等)。 业务和场景的积累,了解测试需求以及易出现的bug的地方。 多维角度设计测试用例(用户、业务流程、异常场景、代码逻辑)。 2、需求分析 …

ccc-pytorch-基础操作(2)

文章目录1.类型判断isinstance2.Dimension实例3.Tensor常用操作4.索引和切片5.Tensor维度变换6.Broadcast自动扩展7.合并与分割8.基本运算9.统计属性10.高阶OP大伙都这么聪明,注释就只写最关键的咯1.类型判断isinstance 常见类型如下: a torch.randn(…

虹科新闻 | 虹科与b-plus正式建立合作伙伴关系,共同致力于用于ADAS/AD系统开发的VV测量解决方案

虹科b-plus 携手共创未来! 近期,虹科与德国b-plus正式建立合作伙伴关系。未来,虹科与b-plus将共同致力于提供用于ADAS/AD系统开发的V&V测量解决方案。 合作寄语 虹科CEO陈秋苑女士表示:“虹科非常期待与b-plus合作&#x…

Microsoft Dynamics 365:导入License到服务层,通过Business Central Administration Shell

本文主要是Microsoft Dynamics 365的License导入的图解干货,不多赘述,直接上图:第一步:准备好的License文件放在你喜欢的目录下第二步:到开始程序里找到并打开 Business Central Administration Shell3.第三步&#xf…

Day895.MySql误删数据还原方案 -MySQL实战

MySql误删数据还原方案 Hi,我是阿昌,今天学习记录的是关于MySql误删数据还原方案的内容。 传统的高可用架构是不能预防误删数据的,因为主库的一个 drop table 命令,会通过 binlog 传给所有从库和级联从库,进而导致整…

ASE20N60-ASEMI的MOS管ASE20N60

编辑-Z ASE20N60在TO-247封装里的静态漏极源导通电阻(RDS(ON))为0.4Ω,是一款N沟道高压MOS管。ASE20N60的最大脉冲正向电流ISM为80A,零栅极电压漏极电流(IDSS)为10uA,其工作时耐温度范围为-55~150摄氏度。ASE20N60功耗…

UVM实战--加法器

前言 这里以UVM实战(张强)第二章为基础修改原有的DUT,将DUT修改为加法器,从而修改代码以使得更加深入的了解各个组件的类型和使用。 一. 组件的基本框架 和第二章的平台的主要区别点 (1)有两个transactio…

我的三周年创作纪念日——学习不止,创作不停

机缘 最开始写文章博客,是为了用输出倒逼自己输入。 从校园离开后,才逐渐意识到学习的不容易。没有写好的教材课程、没有画好的考点重点,没有一起学习的同学,更没有明确的学习方向和路径。 数据分析方向可以学的东西太多了&…

P18 PyTorch 感知机的梯度推导

前言这里面简单介绍一下单层感知机和多层感知机的模型参考:https://www.bilibili.com/video/BV17e4y1q7NG?p41一 单层感知机模型输入: k 代表网络层数,i 代表输入节点的编号前向传播: 权重系数k: 层数i: 前一层输入节点编号j: 当前层输出节点编号这里&a…

软件工程学习

文章目录前言软件特点分类软件工程软件危机项目管理工具总结前言 本博客仅做学习笔记,如有侵权,联系后即刻更改 科普: 软件 软件的定义 软件不是程序,而是程序、数据以及开发、使用和维护程序需要的所有文档的完整集合。 特点 …

windows 安装Qt

下载 下载地址https://download.qt.io/,此文已5.7.0为例子。 根据图片依次选择即可。 安装 安装过程参考另一篇文章Ubuntu 安装 Qt5.7.0即可 配置环境变量 ps:我就是之前没配置环境变量,直接使用创建项目,项目源码直接运行是…

CentOS7安装MariaDB步骤

文章目录1.配置MariaDB yum源2.安装MariaDBMariaDB数据库管理系统是MySQL的一个分支,主要由开源社区在维护,采用GPL授权许可。 MariaDB的目的是完全兼容MySQL,包括API和命令行,使之能轻松成为MySQL的代替品。 CentOS 6 或早期的版…