树状数组(高级数据结构)-蓝桥杯
一、简介
树状数组 (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)------非常好!

相关文章:
树状数组(高级数据结构)-蓝桥杯
一、简介树状数组 (Binary Indexed Tree,BIT),利用数的二进制特征进行检索的一种树状结构。一种真正的高级数据结构: 二分思想、二叉树、位运算、前缀和。高效!代码极其简洁!二、基本应用数列a1,a2,....,an,操作:单点修改…...
Flink-多流转换(Union、Connect、Join)
文章目录多流转换分流基本合流操作联合(Union)连接(Connect)基于时间的合流——双流联结(Join)窗口联结(Window Join)间隔联结(Interval Join)窗口同组联结&a…...
kubeadmin安装k8s集群
目录 一 、环境部署 1、服务器规划 2、环境准备 二、所有节点安装docker 1、配置yum源,安装docker 2、配置daemon.json文件 三、所有节点安装kubeadm、kubelet 和kubectl 四、部署k8s集群 1、查看初始化需要的镜像 2、导入镜像 3、初始化kubeadm 3.1 方…...
java3月train笔记
java笔记 day01 一、jdk和idea下载及安装(一般不建议装C盘): jdk:java开发环境 idea:开发工具(软件),用来编写代码的 苍老师文档服务器:doc.canglaoshi.org jdk下载&…...
Apollo Config原理浅析
文章目录1. 简介2. 基本功能3. Apollo关键功能实现原理3.1 框架整体原理3.1.1 Apollo角色3.1.2 框架执行原理3.1.3 整体组成3.2 细节实现3.2.1 Eureka和不同角色机器的关系3.2.2 Meta Server的作用3.2.3 ReleaseMessage消息实现原理3.2.4 Client的通信方式1. 简介 apollo是携程…...
Kubernetes二 Kubernetes之实战以及pod详解
Kubernetes入门 一 Kubernetes实战 本章节将介绍如何在kubernetes集群中部署一个nginx服务,并且能够对其进行访问。 1.1 Namespace Namespace是kubernetes系统中的一种非常重要资源,它的主要作用是用来实现多套环境的资源隔离或者多租户的资源隔离。…...
机械革命黑苹果改造计划第四番-外接显示器、win时间不正确问题解决
问题 1.无法外接显示器 最大的问题就是目前无法外接显示器,因为机械革命大多数型号笔记本电脑的HDMI、DP接口都是直接物理接在独显上的,内屏用核显外接显示器接独显,英伟达独显也是黑苹果无法驱动的,而且发现机械革命tpyec接口还…...
Linux docker(03)可使用GPU渲染的x11docker实战总结
该系列文章的目的旨在之前的章节基础上,使用x11docker构建一个可以使用GPU的docker容器。该容器可以用于3D图形渲染/XR 等使用GPU渲染的程序调试和运行。 0 why docker 为什么非要用x11docker,而不是其他的docker呢? 因为一般的docker是不…...
【Linux操作系统】【综合实验一 Linux操作基础】
文章目录一、实验目的二、实验要求三、实验内容四、实验报告要求一、实验目的 要求掌握Linux基础操作,熟悉Linux行界面,并明白操作的原理以及目的;熟悉Linux系统环境。 二、实验要求 通过这个第一阶段实验,要求掌握以下操作与相…...
关于监控服务器指标、CPU、内存、警报的一些解决方案
文章目录关于监控服务器指标、CPU、内存、警报的一些解决方案Prometheus Grafana 配置 IRIS / Cach 监控服务器Prometheus简介特点架构图Grafana简介特点配置流程自定义Prometheus接口定义配置 Exporter 监控服务器系统资源简介配置流程使用 Alertmanager报警简介配置流程基于…...
vue3全家桶技术栈基础(一)
在认识vue3全家桶之前,先简单回顾一下vue2的全家桶 一.在vue2中,全家桶技术栈 技术栈: vue2 vue-cli vuex3vue-router3webpack elementUI 1.vue-cli 脚手架构建vue项目,CLI 服务是构建于 webpack 和 webpack-dev-server构建快速生成一个vue2的开发项…...
群晖-第2章-设置HTTPS访问
群晖-第2章-设置HTTPS访问 本章介绍如何通过HTTPS访问群晖,前置要求是完成群晖-第1章-IPV6的DDNS中的内容,可以是IPV4也可以是IPV6,或者你有公网IP,直接添加DNS解析也可以。只要能通过域名访问到nas就行。 本文参考自群晖添加SS…...
005 利用fidder抓取app的api,获得股票数据
一、下载安装fidder 百度搜索fidder直接下载,按提示安装即可。 二、配置fidder 1. 打开fidder,选择tools——options。 2. 选择HTTPS选项卡,勾选前三项,然后点击右侧【actions】,选择【trust root certificate】&a…...
京东测试进阶之路:初入测试碎碎念篇
1、基本的测试用例设计方法 基本的测试用例设计方法(边界值分析、等价类划分等)。 业务和场景的积累,了解测试需求以及易出现的bug的地方。 多维角度设计测试用例(用户、业务流程、异常场景、代码逻辑)。 2、需求分析 …...
华为OD机试 - 乘积最大值(JavaScript) | 机试题+算法思路+考点+代码解析 【2023】
乘积最大值 题目 给定一个元素类型为小写字符串的数组 请计算两个没有相同字符的元素长度乘积的最大值 如果没有符合条件的两个元素返回0 输入 输入为一个半角逗号分割的小写字符串数组 2 <= 数组长度 <= 100 0 < 字符串长度 <= 50 输出 两个没有相同字符的元…...
Java并发知识点
文章目录1. start()和run()方法的区别?2. volatile关键字的作用?使用volatile能够保证:防止指令重排3. sleep方法和wait方法有什么区别?sleep()方法4. 如何停止一个正在运行的线程?方法一:方法二࿱…...
前端 ES6 环境下 require 动态引入图片以及问题
前端 ES6 环境下 require 动态引入图片以及问题require 引入图片方式打包体积对比总结ES6 环境中,通过 require 的方式引入图片很方便,一直以来也没有出过什么问题,后来项目中,需要动态引入图片。 require 动态引入也容易实现&am…...
PCL 欧氏聚类分割
文章目录 一、应用背景1、点云分割算法的属性2、点云分割的挑战二、实现过程三、主要函数及代码实现1、主要函数2、核心代码3、效果实现四、参考文献一、应用背景 1、点云分割算法的属性 1)鲁棒性,比如树木是具有与汽车相区别的特征的,当点云数据的特征数量增加时,分割算…...
一台服务器最大能支持多少条TCP连接
一、一台服务器最大能打开的文件数 1、限制参数 我们知道在Linux中一切皆文件,那么一台服务器最大能打开多少个文件呢?Linux上能打开的最大文件数量受三个参数影响,分别是: fs.file-max (系统级别参数)&am…...
Teradata退出中国,您可以相信中国数据库!
继Adobe、Tableau、Salesforce之后,2023年2月15日,数仓软件巨头Teradata宣布将逐步结束在中国的直接运营。数仓界的“黄埔军校”仓皇撤出中国市场给出的理由非常含蓄:Teradata对中国当前和未来商业环境的慎重评估,我们做了一个艰难…...
docker详细操作--未完待续
docker介绍 docker官网: Docker:加速容器应用程序开发 harbor官网:Harbor - Harbor 中文 使用docker加速器: Docker镜像极速下载服务 - 毫秒镜像 是什么 Docker 是一种开源的容器化平台,用于将应用程序及其依赖项(如库、运行时环…...
模型参数、模型存储精度、参数与显存
模型参数量衡量单位 M:百万(Million) B:十亿(Billion) 1 B 1000 M 1B 1000M 1B1000M 参数存储精度 模型参数是固定的,但是一个参数所表示多少字节不一定,需要看这个参数以什么…...
2025 后端自学UNIAPP【项目实战:旅游项目】6、我的收藏页面
代码框架视图 1、先添加一个获取收藏景点的列表请求 【在文件my_api.js文件中添加】 // 引入公共的请求封装 import http from ./my_http.js// 登录接口(适配服务端返回 Token) export const login async (code, avatar) > {const res await http…...
反射获取方法和属性
Java反射获取方法 在Java中,反射(Reflection)是一种强大的机制,允许程序在运行时访问和操作类的内部属性和方法。通过反射,可以动态地创建对象、调用方法、改变属性值,这在很多Java框架中如Spring和Hiberna…...
C++中string流知识详解和示例
一、概览与类体系 C 提供三种基于内存字符串的流,定义在 <sstream> 中: std::istringstream:输入流,从已有字符串中读取并解析。std::ostringstream:输出流,向内部缓冲区写入内容,最终取…...
CMake控制VS2022项目文件分组
我们可以通过 CMake 控制源文件的组织结构,使它们在 VS 解决方案资源管理器中以“组”(Filter)的形式进行分类展示。 🎯 目标 通过 CMake 脚本将 .cpp、.h 等源文件分组显示在 Visual Studio 2022 的解决方案资源管理器中。 ✅ 支持的方法汇总(共4种) 方法描述是否推荐…...
企业如何增强终端安全?
在数字化转型加速的今天,企业的业务运行越来越依赖于终端设备。从员工的笔记本电脑、智能手机,到工厂里的物联网设备、智能传感器,这些终端构成了企业与外部世界连接的 “神经末梢”。然而,随着远程办公的常态化和设备接入的爆炸式…...
初学 pytest 记录
安装 pip install pytest用例可以是函数也可以是类中的方法 def test_func():print()class TestAdd: # def __init__(self): 在 pytest 中不可以使用__init__方法 # self.cc 12345 pytest.mark.api def test_str(self):res add(1, 2)assert res 12def test_int(self):r…...
JVM虚拟机:内存结构、垃圾回收、性能优化
1、JVM虚拟机的简介 Java 虚拟机(Java Virtual Machine 简称:JVM)是运行所有 Java 程序的抽象计算机,是 Java 语言的运行环境,实现了 Java 程序的跨平台特性。JVM 屏蔽了与具体操作系统平台相关的信息,使得 Java 程序只需生成在 JVM 上运行的目标代码(字节码),就可以…...
使用Spring AI和MCP协议构建图片搜索服务
目录 使用Spring AI和MCP协议构建图片搜索服务 引言 技术栈概览 项目架构设计 架构图 服务端开发 1. 创建Spring Boot项目 2. 实现图片搜索工具 3. 配置传输模式 Stdio模式(本地调用) SSE模式(远程调用) 4. 注册工具提…...
