数据结构 -- 树状数组

前言

树状数组或二叉索引树(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.mfbz.cn/a/692420.html

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

相关文章

Lua移植到标准ANSI C环境

本文目录 1、引言2、环境准备2.1 源码下载2.2 项目构建环境准备 3、项目编译3.1 添加main.c3.2 Kconfig选择模块3.3 项目构建3.4 项目编译 4、运行 文章对应视频教程&#xff1a; 在下方喔 ~~~ 欢迎关注 点击图片或链接访问我的B站主页~~~ lau解释器移植与功能验证 1、引言 本…

RabbitMQ-工作模式(Publish模式Routing模式)

文章目录 发布/订阅&#xff08;Publish/Subscribe&#xff09;交换机临时队列绑定总体代码示例 路由&#xff08;Routing&#xff09;绑定直连交换机多重绑定发送日志订阅总体代码示例 更多相关内容可查看 发布/订阅&#xff08;Publish/Subscribe&#xff09; 构建一个简单的…

达梦8 探寻达梦排序原理:新排序机制(SORT_FLAG=1)

测试版本&#xff1a;--03134283938-20221019-172201-20018 达梦的排序机制由四个dm.ini参数控制&#xff1a; #maximum sort buffer size in Megabytes &#xff0c;有效值范围&#xff08;1~2048&#xff09; SORT_BUF_SIZE 100 #ma…

FinalShell导出服务器配置信息密码password是加密的,如何解密?

本章教程,主要实现了一个小的功能,对FinalShell导出的配置信息,进行解密。 FinalShell导出之后,会产生一个json文件,例如下面这种json格式,里面记录了服务器的IP地址,端口和密码,里面的密码是经过加密处理的,本文主要利用java代码实现对这个password进行解密还原。 {&…

【设计模式】行为型设计模式之 策略模式学习实践

介绍 策略模式&#xff08;Strategy&#xff09;&#xff0c;就是⼀个问题有多种解决⽅案&#xff0c;选择其中的⼀种使⽤&#xff0c;这种情况下我们 使⽤策略模式来实现灵活地选择&#xff0c;也能够⽅便地增加新的解决⽅案。⽐如做数学题&#xff0c;⼀个问题的 解法可能有…

五、身份与访问管理—身份管理和访问控制管理(CISSP)

目录 1.身份管理 1.1 目录技术 1.2 单点登录 1.2.1 Kerberos认证 1.2.2 SESAME认证 1.2.3 KryptoKnight认证 1.3 联合身份管理 1.3.1 SAML安全断言标记语言 1.3.2 标记语言 1.3.3 OpenID 1.3.4 OAuth 1.3.5 OIDC(OpenID Connect) 2.身份即服务(IDaaS) 2.1 AA…

如何提高网站收录?

GSI服务就是专门干这个的&#xff0c;这个服务用的是光算科技自己研发的GPC爬虫池系统。这个系统通过建立一个庞大的站群和复杂的链接结构&#xff0c;来吸引谷歌的爬虫。这样一来&#xff0c;你的网站就能更频繁地被谷歌的爬虫访问&#xff0c;从而提高被收录的机会。 说到效…

【漏洞复现】Apache OFBiz 路径遍历导致RCE漏洞(CVE-2024-36104)

0x01 产品简介 Apache OFBiz是一个电子商务平台&#xff0c;用于构建大中型企业级、跨平台、跨数据库、跨应用服务器的多层、分布式电子商务类应用系统。是美国阿帕奇(Apache)基金会的一套企业资源计划(ERP)系统。该系统提供了一整套基于Java的Web应用程序组件和工具。 0x02 …

【Nacos 2.3.3支持Postgre SQL数据源配置】

Nacos 2.3.3支持Postgre SQL数据源配置 1、Nacos下载2、 插件下载&#xff1a;3、SQL脚本获取、nacos数据库创建、插件编译4、Nacos 集群搭建方式&#xff1a; 1、Nacos下载 下载地址&#xff1a; https://download.nacos.io/nacos-server/nacos-server-2.3.2.zip 或者自行在官…

OrangePi AIpro Ubuntu 22.04 aarch64 安装MySql 8.0

查看MySQL安装包 接下来可以使用以下命令安装MySQL服务器&#xff1a; 安装MySQL 8.0 # 安装最新版本 sudo apt install -y mysql-server # 安装指定版本 sudo apt install -y mysql-server-8.0初始化配置信息 sudo mysql_secure_installationVALIDATE PASSWORD COMPONENT ca…

pc之间的相互通信详解

如图&#xff0c;实现两台pc之间的相互通信 1.pc1和pc2之间如何进行通讯。 2.pc有mac和ip&#xff0c;首先pc1需要向sw1发送广播&#xff0c;sw1查询mac地址表&#xff0c;向router发送广播&#xff0c;router不接受广播&#xff0c;router的每个接口都有ip和mac&#xff0c;…

【Java笔记】第10章:接口

前言1. 接口的概念与定义2. 接口的声明与语法3. 接口的实现4. 接口的继承5. 接口的默认方法6. 接口的静态方法7. 接口的私有方法8. 接口的作用9. 接口与抽象类的区别10. 接口在Java集合中的应用结语 上期回顾:【Java笔记】第9章&#xff1a;三个修饰符 个人主页&#xff1a;C_G…

Java | Leetcode Java题解之第139题单词拆分

题目&#xff1a; 题解&#xff1a; public class Solution {public boolean wordBreak(String s, List<String> wordDict) {Set<String> wordDictSet new HashSet(wordDict);boolean[] dp new boolean[s.length() 1];dp[0] true;for (int i 1; i < s.len…

力扣每日一题85:最大矩形

题目 困难 相关标签 相关企业 给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵&#xff0c;找出只包含 1 的最大矩形&#xff0c;并返回其面积。 示例 1&#xff1a; 输入&#xff1a;matrix [["1","0","1","0",&q…

毫米波SDK使用1

本文档是AM273x等毫米波雷达处理器SDK的配置和使用&#xff0c;主要参考TI的官方文档《mmwave mcuplus sdk user guide》。这里仅摘取其中重要的部分&#xff0c;其余枝节可参考原文。 2 系统概览 mmWave SDK分为两个主要组件:mmWave套件和mmWave演示。 2.1. mmWave套件 mmWa…

react 基础样式的控制(行内和className)

import ./index.cssconst style{color:red,font-size:150px }function App() {return (<div className"App"><h1>行内样式控制</h1><h1 style{{color:red,font-size:150px}} >asd </h1><span style{style} >asd </span>&l…

MATLAB算法实战应用案例精讲-【数模应用】数据孤岛(概念篇)

目录 前言 算法原理 什么是数据孤岛 数据孤岛产生的原因 数据孤岛的问题 什么时候数据孤岛不是坏事&#xff1f; 为什么很难摆脱数据孤岛 数据孤岛对企业造成的负面效应 数据孤岛的影响 数据孤岛的危害 如何解决数据孤岛问题 如何摆脱数据孤岛&#xff1f; 前言 数…

Java学习 - Maven - 常用命令(学习精选)

前言 在上一篇文章中&#xff0c;我们对 Maven 有了初步的了解&#xff0c;包括它的定义、安装步骤以及一些基本的配置方法。Maven 是一个强大的项目管理工具&#xff0c;它可以帮助开发者自动化构建过程&#xff0c;并且管理项目的依赖关系。 今天&#xff0c;我们将深入探讨…

高光谱图像聚类的像素-超像素对比学习与伪标签校正

Pixel-Superpixel Contrastive Learning and Pseudo-Label Correction for Hyperspectral Image Clustering 文章目录 Pixel-Superpixel Contrastive Learning and Pseudo-Label Correction for Hyperspectral Image Clustering摘要引言相关方法对比学习 方法超像素对比学习像素…

攻防世界---misc---Excaliflag

1、题目描述&#xff0c;下载附件是一张图片 2、用winhex分析&#xff0c;没有发现奇怪的地方 3、在kali中使用binwalk -e 命令&#xff0c;虽然分离出来了一些东西&#xff0c;但是不是有用的 4、最后用stegsolve分析&#xff0c;切换图片&#xff0c;发现有字符串&#xff0c…