数据结构: 树状数组

在OI赛事中,数据结构是非常重要的一个内容,更是有人说过,算法+数据结构=程序:
A l g o r i t h m + D a t a Algorithm+Data Algorithm+Data S t r u c t u r e = P r o g r a m m i n g Structure=Programming Structure=Programming
接下来,我们就来介绍一些经典重要的数据结构。
首先是树状数组。

实际上,数据结构就相当于一种算法,是在某种结构上实现某算法。
树状数组是一个查询和修改复杂度都为 O ( l o g 2 n ) O(log_2 n) O(log2n) 的数据结构,运用树状数组可以实现很多算法问题,

比如单点修改,区间求和,求逆序对等等。
比如区间求和,若 n n n 为数列长度, m m m 为查询次数,那么普通查询总和的最坏时间复杂度为 O ( n m ) O(nm) O(nm),假设 n n n m m m < = <= <= 1 0 5 10^{5} 105,时间复杂度就接受不了了,所以很多数据结构比如树状数组,RMQ问题的ST,线段树以及倍增(不太算是数据结构,偏向于 A l g o r i t h m Algorithm Algorithm)之类的,多数情况下都是为了压缩时间复杂度,尽量达到 O ( 1 0 5 − 1 0 7 ) O(10^5-10^7) O(105107)左右,使程序能在 1 s 1s 1s 的时间内求解。
而树状数组的代码效率远远高于线段树,树状数组代码比较少,但线段树代码量特别大

基本思想:

根据任意正整数关于 2 2 2 的不重复次幂的唯一分解性质,若一个正整数 x x x 的二进制表示为 1010 1 ( 2 ) 10101_{(2)} 10101(2),其中 1 1 1 的位是 0 , 2 , 4 0,2,4 0,2,4 ,则 x x x 可以被“二进制分解”成 2 4 + 2 2 + 2 0 2^{4}+2^{2}+2^{0} 24+22+20,进一步,区间 [ 1 , x ] [1,x] [1,x],可以分成 l o g 2 x log_2 x log2x个小区间:

  1. 长度为 2 4 2^4 24 的小区间 [ 1 , 2 4 ] [1,2^{4}] [1,24]
  2. 长度为 2 2 2^2 22 的小区间 [ 2 4 + 1 , 2 4 + 2 2 ] [2^{4}+1,2^{4}+2^{2}] [24+1,24+22]
  3. 长度为 1 1 1 的小区间 [ 2 4 + 2 2 + 1 , 2 4 + 2 2 + 1 ] [2^{4}+2^{2}+1,2^{4}+2^{2}+1] [24+22+1,24+22+1]

树状数组就是基于上述思想的数据结构,基本作用是维护序列的前缀和。
对于区间 [ 1 , x ] [1,x] [1,x],树状数组将其分为 l o g 2 x log_2 x log2x 个小区间, l o g 2 x log_2 x log2x 个子区间的累加和就是 [ 1 , x ] [1,x] [1,x] 的区间和。

基本算法:

由上文可知,这些子区间的共同特点是,若区间结尾为 R R R,则区间长度就等于 R R R 的“二进制分解”下最小的 2 2 2 的次幂,我们设为 l o w b i t ( R ) lowbit(R) lowbit(R)
l o w b i t lowbit lowbit的计算很简单, l o w b i t ( n ) = n lowbit(n)=n lowbit(n)=n & ( − n ) (-n) (n),表示 n n n在二进制表示下最低位的 1 1 1 以及后面的 0 0 0 构成的数。如 l o w b i t ( 10110 0 ( 2 ) ) = 10 0 ( 2 ) = 4 ( 10 ) lowbit(101100_{(2)})=100_{(2)}=4_{(10)} lowbit(101100(2))=100(2)=4(10)
我们就可以写一个子程序函数 l o w b i t lowbit lowbit 来实现:

int lowbit(int x) {return x&(-x);
}

对于序列 A A A,我们建立一个数组 C C C,其中 C C C [ x ] [x] [x] 保存序列 A A A 的区间 [ x − l o w b i t ( x ) + 1 , x ] [x-lowbit(x)+1,x] [xlowbit(x)+1,x] 中所有数之和。
树状数组

我们构造上图所示的结构,满足以下性质:

  1. C C C [ x ] [x] [x] 等于以 x x x 为根的子树中所有叶节点的和。
  2. C C C [ x ] [x] [x] 的叶节点个数等于 l o w b i t ( x ) lowbit(x) lowbit(x)
  3. C C C [ x ] [x] [x] 的父亲节点是 C C C [ x + l o w b i t ( x ) ] [x+lowbit(x)] [x+lowbit(x)]
  4. 深度为 l o g 2 N log_2 N log2N
    如图我们可以知道:
    C C C [ 1 ] [1] [1] = A [ 1 ] A[1] A[1]
    C C C [ 2 ] [2] [2] = A [ 1 ] A[1] A[1] + A [ 2 ] A[2] A[2]
    C C C [ 3 ] [3] [3] = A [ 3 ] A[3] A[3]
    C C C [ 4 ] [4] [4] = A [ 1 ] A[1] A[1] + A [ 2 ] A[2] A[2] + A [ 3 ] A[3] A[3] + A [ 4 ] A[4] A[4]
    C C C [ 5 ] [5] [5] = A [ 5 ] A[5] A[5]
    C C C [ 6 ] [6] [6] = A [ 5 ] A[5] A[5] + A [ 6 ] A[6] A[6]
    C C C [ 7 ] [7] [7] = A [ 7 ] A[7] A[7]
    C C C [ 8 ] [8] [8] = A [ 1 ] A[1] A[1] + A [ 2 ] A[2] A[2] + A [ 3 ] A[3] A[3] + A [ 4 ] A[4] A[4] + A [ 5 ] A[5] A[5] + A [ 6 ] A[6] A[6] + A [ 7 ] A[7] A[7] + A [ 8 ] A[8] A[8]

对某个单点的元素进行修改

就先讲加法操作
树状数组支持单点加法操作,根据树状数组的结构特性,节点 x x x 及其所有祖先节点的 C C C 值会受到操作的影响,而任意一个节点的祖先最多有 l o g 2 N log_2 N log2N 个,逐一对 C C C 值进行加法就行了。时间复杂度为 O ( l o g 2 N ) O(log_2 N) O(log2N)
Code:

void update(int x,int y) {  //将第x个数加上yfor(;x<=N;x+=lowbit(x))  c[x]+=y;
}

而要将某个单点的元素直接改成 y y y,则需要如下代码:

void update(int x,int y) {  //将第x个数改成yfor(int i=x;i<=N;i+=lowbit(i))  c[i]+=(y-a[i]);
}

查询前缀和

树状数组支持查询前缀和,较为简单,时间复杂度为 O ( l o w 2 N ) O(low_2 N) O(low2N) 直接给出
Code:

long long ask_sum(int x) {  //函数名各式各样//查询前x个数的和long long ans=0;for(;x;x-=lowbit(x))  ans+=c[x];return ans;
}

接下来,我们用一道简单的例题来详细讲解一下树状数组

例题

单点修改区间查询
[题目描述]

已知一个数列,你需要进行下面两种操作:

  1. 将某个数加上 x x x
  2. 求出某区间所有数的和。
输入格式

第一行两个整数 n , m n,m n,m, 分别表示该数列长度和操作个数
第二行 n n n 个整数,表示原数列。
接下来 m m m 行每行包含 3 3 3 个整数,表示一个操作,具体如下:
第一个整数为opt,有下列两种输入情况
1 x k: 将第 x x x 个数加上 k k k
2 x y: 询问区间 [ x , y ] [x,y] [x,y] 所有数的和
输出格式
对于每个opt=2,输出一行一个整数,表示相应的结果。

数据范围

1 1 1 < = <= <= n , m n,m n,m < = <= <= 1 0 6 , 10^{6}, 106, 0 0 0 < = <= <= ∣ a [ i ] ∣ , x |a[i]|,x a[i],x < = <= <= 1 0 6 10^{6} 106

树状数组模板题,只是操作2不是求前缀和,是某个区间 [ x , y ] [x,y] [x,y] 的和,我们用 a s k _ s u m ( y ) − a s k _ s u m ( x − 1 ) ask \_ sum(y)-ask \_ sum(x-1) ask_sum(y)ask_sum(x1) 就可以了。
Code:

#include<bits/stdc++.h>
int n,q,opt;
long long a[10000001],c[10000001];
long long x,y;
inline int lowbit(int x) {  //lowbit函数return x&(-x);
}
inline void update(int x,long long k) {for(;x<=n;x+=lowbit(x))  c[x]+=k;
}
inline long long ask_sum(int x) {long long ans=0;for(;x;x-=lowbit(x))  ans+=c[x];return ans;
}
int main() {std::cin>>n>>q;for(int i=1;i<=n;i++)  scanf("%lld",a+i),update(i,a[i]);  //输入while(q--) {scanf("%d %lld %lld",&opt,&x,&y);switch(opt) {case 1:  //当opt=1时将某个单点元素加上yupdate(x,y); break;case 2:  //当等于2时查询某个区间所有数的和printf("%lld\n",ask_sum((int)y)-ask_sum((int)x-1)); break;}}
}

树状数组的模板是非常重要的,虽然说理解也很重要,但在背诵的同时理解的效率会更高。
这篇介绍树状数组的文章到此结束了,如有bug请指出,不胜感激!
下一篇数据结构的文章介绍线段树

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

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

相关文章

如何在 Ubuntu 系统中安装PyCharm集成开发环境?

在上一篇文章中&#xff0c;我们探讨了Jupyter notebook&#xff0c;今天再来看看另一款常用的Python 工具&#xff0c;Pycharm。 PyCharm也是我们日常开发和学习常用的Python 集成开发环境 (IDE)&#xff0c;由 JetBrains 开发。 PyCharm 带有一整套可以帮助用户在使用Pytho…

docker映射了端口,宿主机不生效

1、问题产生原因 docker run -d --name my-redis -p 6379:6379 -v /usr/redis.conf:/usr/local/etc/redis/redis.conf team-redis:3.2 redis-server /usr/local/etc/redis/redis.conf 这容器跑起来了&#xff0c;端口6379没用。搞的我一直怀疑哪里出错了&#xff0c;查看配置…

【网络安全】服务基础第一阶段——第二节:网络测试与用户

一、Windows网络测试工具 CMD&#xff08;命令提示符&#xff09;中&#xff0c;ping和tracert是两个非常有用的网络诊断工具 1.1.ping命令 ping命令是Windows和其他操作系统中用于测试主机之间网络连接是否可达的基本命令行工具。它通过发送ICMP&#xff08;Internet Contr…

CSS中的元素布局与定位详细说明

1、前言 在CSS开发中&#xff0c;很重要的一个工作就是根据UI设计稿&#xff0c;进行元素的布局与定位&#xff0c;使得元素&#xff08;比如某一段文本、按钮、图片等&#xff09;显示在页面正确的位置。本文就元素的布局与定位方面&#xff0c;做一些讲解和说明。 2、元素的…

Markdown 美化 Github 个人主页

注&#xff1a;本文参考这篇博客 http://t.csdnimg.cn/KXhSw 目录 1 效果展示2 创建仓库3 编写 Markdown3.1 动态波浪图3.2 打字机动图3.3 技术栈图标3.4 项目贡献统计3.5 连续贡献统计3.6 贡献统计图3.7 代码时长统计3.8 仓库代码占比 1 效果展示 先来看看效果&#xff1a; 动…

OSPF路由配置--多区域

目录 不理解OSPF路由动态协议的可以回顾一下OSPF详解&#xff0c;下这一系列的实验都不再做解释,直接开始配置 一. 实验拓扑 二. 实验配置 (命令可以直接复制粘贴到CLI中) 三. 实验验证 不理解OSPF路由动态协议的可以回顾一下OSPF详解&#xff0c;下这一系列的实验都不…

C++ 设计模式——迭代器模式

迭代器模式 C 设计模式——迭代器模式1. 主要组成成分2. 迭代器模式范例2.1 抽象迭代器2.2 抽象容器2.3 具体的迭代器2.4 具体的容器2.5 主函数示例 3. 迭代器 UML 图3.1 迭代器 UML 图解析 4. 迭代器模式的优点5. 迭代器模式的缺点6. 迭代器模式的适用场景7. 现代C中的迭代器总…

【深度学习】使用Conda虚拟环境安装多个版本的CUDA和CUDNN方便切换

conda虚拟环境安装CUDA和CUDNN 官网教程 https://docs.nvidia.com/cuda/cuda-installation-guide-linux/index.html#conda-installation 1. 背景 深度学习用显卡训练的时候&#xff0c;需要安装与显卡对应的cuda和cudnn。但不同的项目所支持的pytorch版本是不一样的&#x…

Openssl Infinite Loop 漏洞(CVE-2022-0778)

Openssl Infinite Loop 漏洞&#xff08;CVE-2022-0778&#xff09; 1. 漏洞详情 在该漏洞中由于证书解析时使用的 BN_mod_sqrt() 函数存在一个错误&#xff0c;它会导致在非质数的情况下永远循环。可通过生成包含无效的显式曲线参数的证书来触发无限循环。由于证书解析是在验…

视频监控汇聚算法平台训练站车辆类型算法分析车辆类型检测应用方案

车辆类型检测算法是计算机视觉和深度学习技术在交通管理和智能车辆系统中的重要应用之一。这种算法通过自动分析和识别车辆图像&#xff0c;能够准确判断车辆的类型&#xff0c;如轿车、SUV、货车等。 运用方案 数据采集与预处理 采集包含车辆的图像或视频数据&#xff0c;包…

自学成才

软件只是一种工具&#xff0c;正如给你一张纸和一支笔&#xff0c;有人满纸疙瘩&#xff0c;有人行云流水唱成一曲绝唱&#xff0c;全在于笔头功夫。使用软件一样需要智慧&#xff0c;不光是懂了就行&#xff0c;还得创造性使用&#xff0c;才会成就别人望洋兴叹的绝活。 Core…

【实施】软件实施方案(word套用)

软件实施方案 二、 项目介绍 三、 项目实施 四、 项目实施计划 五、 人员培训 六、 项目验收 七、 售后服务 八、 项目保障措施 软件开发全套资料获取&#xff1a;&#xff08;本文末个人名片也可直接获取&#xff09; 软件产品&#xff0c;特别是行业解决方案软件产品不同于一…

【Electron】桌面应用开发electron-builder打包报错问题处理

Electron 桌面应用开发electron-builder打包过程中各种报错问题处理 前一篇有写过 Electron 桌面应用开发快速入门到打包Windows应用程序 在安装到打包的整个过程中&#xff0c;我们都会遇到很多诡异的问题&#xff0c;接下来我将介绍我遇到的几个问题的解决方案 一、拉包的时…

VBA技术资料MF191:将源文件夹所有文件移动到目标文件夹

我给VBA的定义&#xff1a;VBA是个人小型自动化处理的有效工具。利用好了&#xff0c;可以大大提高自己的工作效率&#xff0c;而且可以提高数据的准确度。“VBA语言専攻”提供的教程一共九套&#xff0c;分为初级、中级、高级三大部分&#xff0c;教程是对VBA的系统讲解&#…

iOS profiles文件过期如何更新

创建发布用的Certificates 首先进入到https://developer.apple.com/account页面选择【证书】进入【新建证书】页面 点击【新建证书】按钮&#xff1a; 根据需求选中对应的【证书类型】&#xff0c;我选的是【Apple Distribution】&#xff0c; 开发者证书选择【Apple Devel…

react antd TreeSelect实现自定义标签

<ProFormTreeSelectlabel"接收对象"name"receiverObjects"colProps{{ span: 16 }}labelCol{{span: 6,}}wrapperCol{{span: 18,}}rules{[{ required: true }]}fieldProps{{showSearch: true,multiple: true,// autoClearSearchValue: true,filterTreeNod…

探索条形码与二维码的秘密:pyzbar库的神奇之旅

文章目录 探索条形码与二维码的秘密&#xff1a;pyzbar库的神奇之旅背景&#xff1a;为什么选择pyzbar&#xff1f;pyzbar是什么&#xff1f;如何安装pyzbar&#xff1f;简单库函数使用方法场景应用常见Bug及解决方案总结 探索条形码与二维码的秘密&#xff1a;pyzbar库的神奇之…

数字化与进制转换

1.数字化是什么&#xff1f; 数字化是将事物的属性转化为计算机可处理对象的过程。 2.数字化的好处&#xff1f; 可以让我们的生活&#xff0c;学习和工作更加便捷&#xff0c;大大提升我们学习和工作的效率。 3.如何将采集到的数据进行数字化&#xff1f; 可以通过两种信…

爬取央视热榜并存储到MongoDB

1. 环境准备 在开始之前&#xff0c;确保你已经安装了以下Python库&#xff1a; pip install requests pymongo2. 爬取网页内容 首先&#xff0c;我们需要爬取央视热榜的网页内容。通过requests.get()方法&#xff0c;我们可以获取网页的HTML内容&#xff0c;并通过re.finda…

Linux--gdb的常用命令

目录 前言 一、gdb是什么&#xff1f; 二、常用命令 前言 提示&#xff1a;这里可以添加本文要记录的大概内容&#xff1a; 对于程序有两个版本&#xff0c;一个是debug版和release版&#xff0c;要想进行调试必须使用debug版本&#xff0c;再Linux上进行调试就要用到调试器…