数据结构 -- 树状数组

前言

树状数组或二叉索引树(Binary Indexed Tree),又以其发明者命名为 Fenwick 树。其初衷是解决数据压缩里的累积频率的计算问题,现多用于高效计算数列的前缀和、区间和。它可以以 O(logn) 的时间得到任意前缀和。并同时支持在 O(logn) 时间内支持动态单点值的修改。空间复杂度 O(n)。

介绍

1.原理

树状数组,顾名思义是树状的数组,我们首先引入二叉树,叶子节点代表A[1]~A[8]。
在这里插入图片描述
现在变形一下:
在这里插入图片描述

现在定义每一列的顶端节点C数组(其实C数组就是树状数组),如图:
在这里插入图片描述
理解树状数组的重点
C[i]代表子树的叶子节点的权值之和,如图可以知道:

C[1]=A[1];

C[2]=A[1]+A[2];

C[3]=A[3];

C[4]=A[1]+A[2]+A[3]+A[4];

C[5]=A[5];

C[6]=A[5]+A[6];

C[7]=A[7];

C[8]=A[1]+A[2]+A[3]+A[4]+A[5]+A[6]+A[7]+A[8];

看过上面的列表,有没有看出来什么规律来呢?

如果没有看出来,那说明你不知道lowbit函数。

先看lowbit函数的代码:

function lowBit(x){return x&-x;
}

不知道干啥的吧!是不是一脸懵逼?别慌,举几个例子:

1 & -1 = 1;
2 & -2 = 2;
3 & -3 = 1;
4 & -4 = 4;
5 & -5 = 1;
6 & -6 = 2;
7 & -7 = 1;
8 & -8 = 8;

对比上面的,熟悉不,看出来规律了吗?

怎么理解呢?

lowbit函数的含义即为:x(二进制)最低位1后面的0组成的数
例如:
5(二进制:101)最低位1后面0的个数为0,则lowbit(5)=2^0=1(十进制)
12(二进制:1100) 最低位1后面0的个数为2,则lowbit(12)=2^2=4(十进制)

那现在我给你一个数组,让你求解他的树状数组,能求出来吗?思考一下解出来了就跳过下面。或者对一下答案!

var A = [1,2,3,4,5,6,7,8]var C = new Array(9).fill(0);function getSum(i) {  let begin = lowBit(i);let res=0;while(begin) {res += A[i-begin];begin --;}return res;
}for(let i=1;i<9;i++){C[i] = getSum(i);
}
console.log("树状数组",treeArr);
//[0,1, 3, 3, 10, 5, 11, 7, 36]
//注意哦我不要第一项,至于为什么,懂得都懂。

2.应用

2.1 区间查询

利用C[i]数组,求A数组中前i项和,举两个栗子:

前7项和:
sum[7]=A[1]+A[2]+A[3]+A[4]+A[5]+A[6]+A[7];
而C[4]=A[1]+A[2]+A[3]+A[4];C[6]=A[5]+A[6];C[7]=A[7];
可以得到:sum[7]=C[4]+C[6]+C[7]。
数组下标写成二进制:sum[(111)]=C[(100)]+C[(110)]+C[(111)];

前5项和:
sum[5]=A[1]+A[2]+A[3]+A[4]+A[5];
而C[4]=A[1]+A[2]+A[3]+A[4];C[5]=A[5];
可以得到:sum[5]=C[4]+C[5];
数组下标写成二进制:sum[(101)]=C[(100)]+C[(101)];

细细观察二进制,树状数组追其根本就是二进制的应用,结合代码演示一下代码过程:

function finSum(i){let res = 0;while(i){res += treeArr[i];i -= lowBit(i)}return res;
}
console.log("前5项和",finSum(5)); //15
console.log("前7项和",finSum(7)); //28

代码推演:
lowbit(5)=001 5-lowbit(5)=4(100) ans+=C[4]
lowbit(4)=100 4-lowbit(4)=0(000) break;

看到这里是不是有点疑惑,这不比前缀算法还多算了一个树状数组吗?我也有这个疑问,保留意见,先继续往下看。

2.2 单点更新
当我们修改A数组中某个值时,应当如何更新C数组呢?回想一下,区间查询的过程,再看一下上文中列出的过程。这里声明一下:单点更新实际上是不修改A数组的,而是修改树状数组C,向上更新区间长度为lowbit(i)所代表的节点的值。

function update(i,k){A[i] += k;while(i <= 8){C[i] += k;i += lowBit(i);}
}
update(6,5);console.log("前5项和",finSum(5)); //15
console.log("前7项和",finSum(7)); //33

在这里插入图片描述

如上图:若在A[1]加上值val,即更新A[1]时,需要向上更新C[1],C[2],C[4],C[8],这个时候只需将这4个节点每个节点的值加上val即可。这里为了方便大家理解,人为添加了个A数组表示每个叶子节点的值,事实上A数组并不用修改,实际运用中也可不设置A数组,单点更新只需修改树状数组C即可。下标写成二进制:C[(001)],C[(010)],C[(100)],C[(1000)];

lowbit(1)=001 1+lowbit(1)=2(010) C[2]+=val;

lowbit(2)=010 2+lowbit(2)=4(100) C[4]+=val;

lowbit(4)=100 4+lowbit(4)=8(1000) C[8]+=val;

由于c[1] c[2] c[4] c[8] 都包含有A[1],所以在更新A[1]时实际上就是更新每一个包含A[1]的节点。

现在是不是有点懵懂了,如果用前缀和的话,需要在1后面的所有元素都加上val,但是对于树状数组就不同了。时间复杂度为O(logN)

与线段树对比

1.两者在复杂度上同级, 但是树状数组的常数明显优于线段树, 其编程复杂度也远小于线段树.
2.树状数组的作用被线段树完全涵盖, 凡是可以使用树状数组解决的问题, 使用线段树一定可以解决, 但是线段树能够解决的问题树状数组未必能够解决.
3. 树状数组的突出特点是其编程的极端简洁性, 使用lowbit技术可以在很短的几步操作中完成树状数组的核心操作,其代码效率远高于线段树。

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

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

相关文章

计算机毕业设计python+spark知识图谱音乐推荐系统 音乐数据分析可视化大屏 音乐爬虫 LSTM情感分析 大数据毕设 深度学习 机器学习

流程&#xff1a; 1.Python采集网易云音乐歌手、歌词、音乐、评论等约10-20万海量数据&#xff0c;存入mysql数据库&#xff1b; 2.使用pandasnumpy/MapReduce对mysql中四类数据进行数据清洗&#xff0c;写入.csv文件并上传至hdfs(含评论NLP文本分类/lsm情感分析); 3.使用hive建…

关于科技的总结与思考

文章目录 互联网时代有趣的数字数据驱动大数据的两个特性数据保护互联网免费模式的再探讨平台互联网的意义人工智能伦理的思考语言理性人梅特卡夫定律冲浪的神奇之处AR的恐怖之处叙词表、受控词表和大众分类法六度/十九度的解读知识图谱是真正的仿生智能幂次法则和优先连接现代…

MyBatis插件机制

MyBatis插件机制是该框架提供的一种灵活扩展方式&#xff0c;允许开发者在不修改框架源代码的情况下对MyBatis的功能进行定制和增强。这种机制主要通过拦截器&#xff08;Interceptor&#xff09;实现&#xff0c;使得开发者可以拦截和修改MyBatis在执行SQL语句过程中的行为。 …

【AI大模型】Transformers大模型库(五):AutoModel、Model Head及查看模型结构

目录​​​​​​​ 一、引言 二、自动模型类&#xff08;AutoModel&#xff09; 2.1 概述 2.2 Model Head&#xff08;模型头&#xff09; 2.3 代码示例 三、总结 一、引言 这里的Transformers指的是huggingface开发的大模型库&#xff0c;为huggingface上数以万计的预…

ChatGPT Prompt技术全攻略-总结篇:Prompt工程技术的未来发展

系列篇章&#x1f4a5; No.文章1ChatGPT Prompt技术全攻略-入门篇&#xff1a;AI提示工程基础2ChatGPT Prompt技术全攻略-进阶篇&#xff1a;深入Prompt工程技术3ChatGPT Prompt技术全攻略-高级篇&#xff1a;掌握高级Prompt工程技术4ChatGPT Prompt技术全攻略-应用篇&#xf…

DNS协议 | NAT技术 | 代理服务器

目录 一、DNS协议 1、DNS背景 2、DNS协议 域名 域名解析 二、NAT技术 1、NAT技术 2、NAPT技术 3、NAT技术的缺陷 三、代理服务器 1、正向代理服务器 2、反向代理服务器 一、DNS协议 域名系统&#xff08;Domain Name System&#xff0c;缩写&#xff1a;DNS&#…

20240605解决飞凌的OK3588-C的核心板刷机原厂buildroot不能连接ADB的问题

20240605解决飞凌的OK3588-C的核心板刷机原厂buildroot不能连接ADB的问题 2024/6/5 13:53 rootrootrootroot-ThinkBook-16-G5-IRH:~/repo_RK3588_Buildroot20240508$ ./build.sh --help rootrootrootroot-ThinkBook-16-G5-IRH:~/repo_RK3588_Buildroot20240508$ ./build.sh lun…

【学术小白成长之路】02三方演化博弈(基于复制动态方程)期望与复制动态方程

从本专栏开始&#xff0c;笔者正式研究演化博弈分析&#xff0c;其中涉及到双方演化博弈分析&#xff0c;三方演化博弈分析&#xff0c;复杂网络博弈分析等等。 先阅读了大量相关的博弈分析的文献&#xff0c;总结了现有的研究常用的研究流程&#xff0c;针对每个流程进行拆解。…

快速搭建rtsp server(Ubuntu)

在现代视频监控和实时视频流媒体应用中&#xff0c;实时流协议&#xff08;RTSP&#xff09;服务器扮演着至关重要的角色。无论是家庭安防系统、企业级监控还是流媒体服务&#xff0c;RTSP服务器都能提供高效、稳定的解决方案。然而&#xff0c;对于许多初学者或开发者来说&…

数学建模笔记

数学建模 定义角度 数学模型是针对参照某种事物系统的特征或数量依存关系&#xff0c;采用数学语言&#xff0c;概括地或近似地表述出的一种数学结构&#xff0c;这种数学结构是借助于数学符号刻画出来的某种系统的纯关系结构。从广义理解&#xff0c;数学模型包括数学中的各…

高考分数查询结果自动推送至微信(卷II)

祝各位端午节安康&#xff01;只要心中无结&#xff0c;每天都是节&#xff0c;开心最重要&#xff01; 在上一篇文章高考分数查询结果自动推送至微信&#xff08;卷Ⅰ&#xff09;-CSDN博客中谈了思路&#xff0c;今天具体实现。文中将敏感信息已做处理&#xff0c;读者根据自…

【大学物理】波动光学:光的衍射

23.2 单缝的夫琅禾费衍射_哔哩哔哩_bilibili 1 光的衍射和惠更斯-菲涅尔原理 干涉vs衍射&#xff1a;干涉研究的是两个分立的子光源&#xff0c;衍射研究的是连续的子光源。 两位科学家用分解的思想&#xff0c;一个解决了方向一个解决了光强。 2 单缝的夫琅禾费衍射 夫琅禾…

【SpringBoot + Vue 尚庭公寓实战】项目初始化准备(二)

【尚庭公寓SpringBoot Vue 项目实战】项目初始化准备&#xff08;二&#xff09; 文章目录 【尚庭公寓SpringBoot Vue 项目实战】项目初始化准备&#xff08;二&#xff09;1、导入数据库2、创建工程3、项目初始配置3.1、SpringBoot依赖配置3.2、创建application.yml文件3.3、…

基于Java+SpringBoot制作一个景区导览小程序

基于Java+SpringBoot制作一个景区导览小程序。其中系统前端功能包括注册登录、景区采风、旅游导览、地图导航、发布采风、门票预订、修改个人信息;系统后台功能包括用户管理、景区管理、采风管理等模块。 摘要一、小程序1. 创建小程序2. 首页3. 景区采风页4. 旅游导览页5. 发布…

vmware-17虚拟机安装教程,安装linux centos系统

下载VMware 1.进入VMware官网&#xff1a;https://www.vmware.com/sg/products/workstation-pro.html 2.向下翻找到&#xff0c;如下界面并点击“现在安装” 因官网更新页面出现误差&#xff0c;现提供vmware17安装包网盘链接如下&#xff1a; 链接&#xff1a;https://pan.b…

Ubuntu22.04 下 pybind11 搭建,示例

Pybind11 是一个轻量级的库&#xff0c;用于在 C 中创建 Python 绑定。Ubuntu22下安装pybind11步骤如下&#xff1a; 1. 安装 pybind11 1.1 pip 命令安装 pip3 install pybind11 1.2 源代码安装 安装依赖库&#xff1a; sudo pip install -i https://pypi.tuna.tsinghua.e…

人工智能和物联网如何结合

欢迎来到 Papicatch的博客 目录 ​ &#x1f349;引言 &#x1f349;AI与IoT的结合方式 &#x1f348;数据处理和分析 &#x1f34d;实例 &#x1f348;边缘计算 &#x1f34d;实例 &#x1f348;自动化和自主操作 &#x1f34d;实例 &#x1f348;安全和隐私保护 &…

Qt窗口与对话框

目录 Qt窗口 1.菜单栏 2.工具栏 3.状态栏 4.滑动窗口 QT对话框 1.基础对话框QDiaog 创建新的ui文件 模态对话框与非模态对话框 2.消息对话框 QMessageBox 3.QColorDialog 4.QFileDialog文件对话框 5.QFontDialog 6.QInputDialog Qt窗口 前言&#xff1a;之前以上…

【JAVASE】JAVA应用案例(下)

一&#xff1a;抢红包 一个大V直播时&#xff0c;发起了抢红包活动&#xff0c;分别有9,666,188,520,99999五个红包。请模拟粉丝来抽奖&#xff0c;按照先来先得&#xff0c;随机抽取&#xff0c;抽完即止&#xff0c;注意&#xff1a;一个红包只能被抽一次&#xff0c;先抽或…

输入偏置电流是什么?

输入失调电流与输入补偿电流概念一样&#xff08;input offset current&#xff09;&#xff1a;同相减去反相输入端偏置电流的差值。这是由生产工艺导致同相与反相端的电流大小方向都会有所不同。 第一种情况&#xff1a;同相输入端减去反相输入端 第一种情况&#xff1a;同相…