智能摘要文章源自JAVA秀-https://www.javaxiu.com/27787.html
求和是树状数组中的一个应用,并不是只能求和,本文使用求和作为例子。r]表示从下标l开始,到r结束的区间,包含l和r。我们可以看出,4在3头上,8在4头上,16在8头上。我们只需要找到一种方式,得到一个块头上的块,然后使用循环能推出整串。以上的"幻想"只是存在于树已经有了之后,如何根据数组a(原始数组),来构造一棵树呢?文章源自JAVA秀-https://www.javaxiu.com/27787.html
原文约 2122 字 | 图片 18 张 | 建议阅读 5 分钟 | 评价反馈文章源自JAVA秀-https://www.javaxiu.com/27787.html
什么是树状数组?让这个12岁年轻人为你讲解
小黑格子屋 文章源自JAVA秀-https://www.javaxiu.com/27787.html
以下文章来源于程序员小灰,作者Cat-shao文章源自JAVA秀-https://www.javaxiu.com/27787.html
文章源自JAVA秀-https://www.javaxiu.com/27787.html 文章源自JAVA秀-https://www.javaxiu.com/27787.html 程序员小灰文章源自JAVA秀-https://www.javaxiu.com/27787.html 一群喜爱编程技术和算法的小仓鼠。文章源自JAVA秀-https://www.javaxiu.com/27787.html
文章源自JAVA秀-https://www.javaxiu.com/27787.html
来源:程序员小灰文章源自JAVA秀-https://www.javaxiu.com/27787.html
作者:Cat-shao文章源自JAVA秀-https://www.javaxiu.com/27787.html
作者Cat-shao,真名邵振轩,辽宁OIer,年仅12岁,非常感谢他的投稿。文章源自JAVA秀-https://www.javaxiu.com/27787.html
Part 1 我学它干啥?
树状数组,Binary Indexed Tree(简称BIT),是由Peter M. Fenwick在1994年发明的——百度百科文章源自JAVA秀-https://www.javaxiu.com/27787.html
名字十分高大上,那么它是干什么的呢?文章源自JAVA秀-https://www.javaxiu.com/27787.html
求和
求和是树状数组中的一个应用,并不是只能求和,本文使用求和作为例子。文章源自JAVA秀-https://www.javaxiu.com/27787.html
现在有一个数组a,我们需要求很多次数组中不同区间的和,而且多次对a中随意一项进行更改。比如说a = {0, 1, 5, 3, 2, 4}
文章源自JAVA秀-https://www.javaxiu.com/27787.html
第一次求[1, 3]
,得到1 + 5 + 3 = 9
第二次求[2, 4]
,得到5 + 3 + 2 = 10
第三次,这时候我把a[2] += 2
第四次求[1, 5]
,得到1 + 7 + 3 + 2 + 4 = 17
文章源自JAVA秀-https://www.javaxiu.com/27787.html
[l, r]
表示从下标l开始,到r结束的区间,包含l和r。l: leftr: right文章源自JAVA秀-https://www.javaxiu.com/27787.html
这时候很多同学想到的第一个方法,就是直接挨个加起来不就好了吗?文章源自JAVA秀-https://www.javaxiu.com/27787.html
可此题暗藏玄机,我们要进行多次求和啊,每一次都重新计算太慢,能不能提前加好一些区域,反复使用呢?文章源自JAVA秀-https://www.javaxiu.com/27787.html
这就要请出我们的主角了——树状数组文章源自JAVA秀-https://www.javaxiu.com/27787.html
Part 2 lowbit
树状数组的结构十分精妙,其中离不开一个基本运算——lowbit文章源自JAVA秀-https://www.javaxiu.com/27787.html
文章源自JAVA秀-https://www.javaxiu.com/27787.html
lowbit(i)
可以解释为:i中最低位的1以及后面的0;或者你可以把它理解成i能被n整除,n还可以写成2k文章源自JAVA秀-https://www.javaxiu.com/27787.html
一种lowbit的实现方式为lowbit(x) = x & -x
文章源自JAVA秀-https://www.javaxiu.com/27787.html
longlonglowbit(longlong x){return x &-x;}
还是拿172举例子,化成二进制后我们发现除了尾部的100
相同之外,其他位都不同,使用按位与
能得到lowbit的值文章源自JAVA秀-https://www.javaxiu.com/27787.html
Part 3 树状数组
既然名字叫树状数组,那它必然是个数组,可外表下藏着二叉树的结构。精巧的结构与lowbit密不可分,真是妙极了。文章源自JAVA秀-https://www.javaxiu.com/27787.html
以下内容中,我们在这里管原始的数组叫做a,树状数组(经过处理)叫做bit,三个图中的数字均为下标,不是值!文章源自JAVA秀-https://www.javaxiu.com/27787.html
结构
文章源自JAVA秀-https://www.javaxiu.com/27787.html
bit中存放了多个数的和,那么具体存了几个,在哪里呢?我们规定,bit[i]
中存从右往左数lowbit(i)
个数。文章源自JAVA秀-https://www.javaxiu.com/27787.html
bit[i] = 在数组a中从 i - lowbit(i) + 1 到 i 求和
文章源自JAVA秀-https://www.javaxiu.com/27787.html
更改单个数值
文章源自JAVA秀-https://www.javaxiu.com/27787.html
首先,更改数据可以转换成加法,我们这里讨论加法,和更改是一样的。文章源自JAVA秀-https://www.javaxiu.com/27787.html
挨个加起来时,更改a[i]只需要动它一个就可以了。可是在树状数组中,可能有好几项,都包括这个a[i]。文章源自JAVA秀-https://www.javaxiu.com/27787.html
拿a[3]来举例子吧。文章源自JAVA秀-https://www.javaxiu.com/27787.html
bit[3] 对应 a的[3, 3] 的和bit[4] 对应 a的[1, 4] 的和bit[8] 对应 a的[1, 8] 的和bit[16] 对应 a的[1, 16] 的和以上四个bit中的值都需要更改
在图中,我们可以看出,4在3头上,8在4头上,16在8头上。我们只需要找到一种方式,得到一个块 头上的块,然后使用循环能推出整串。文章源自JAVA秀-https://www.javaxiu.com/27787.html
如何找到自己头上的数呢?文章源自JAVA秀-https://www.javaxiu.com/27787.html
图中的6和橘色没关系,是第二组例子文章源自JAVA秀-https://www.javaxiu.com/27787.html
我们发现,在当前块的位置
加上当前块的长度
之后能跳到头上。我是这么理解的:加上一个当前块后会把局部的空缺补上,合并成了一块,而这块也许也补了更大的空缺,这样就一次跳了好几级
文章源自JAVA秀-https://www.javaxiu.com/27787.html
上文定义规定了第i个块长度 = lowbit(i)
,拿来用即可。文章源自JAVA秀-https://www.javaxiu.com/27787.html
c++实现:文章源自JAVA秀-https://www.javaxiu.com/27787.html
voidadd(int index,longlong value){while(index <= n){// 更新直到最大的块 node[index]+= value;// 更新当前的块 index +=lowbit(index);// 加上一个自己的长度,补上空缺,得到下一个块}}
区间求和
文章源自JAVA秀-https://www.javaxiu.com/27787.html
先考虑[1, r]
的求和从右往左取块,将块代表的数值加起来即可文章源自JAVA秀-https://www.javaxiu.com/27787.html
图中的例子:文章源自JAVA秀-https://www.javaxiu.com/27787.html
第一次取到13,长度为
lowbit(13) = 1
第二次13取完了从12开始取,长度为4,一次性将[9, 12]
取完第三次[9, 13]
取完了从8开始,长度为8,取走[1, 8]
,到此[1, 13]
全部取走文章源自JAVA秀-https://www.javaxiu.com/27787.html
c++实现文章源自JAVA秀-https://www.javaxiu.com/27787.html
longlongsum(int index){longlong sum =0;while(index >0) { sum += node[index]; index -=lowbit(index);}return sum;}
那如果求和左端点不在1处呢?文章源自JAVA秀-https://www.javaxiu.com/27787.html
对[l, r]
求和,可以写成sum(r) - sum(l - 1)
先把大区域[1, r]
求出来,然后扣掉[1, l - 1]
的部分,不就是[l, r]
吗?文章源自JAVA秀-https://www.javaxiu.com/27787.html
构造
文章源自JAVA秀-https://www.javaxiu.com/27787.html
以上的“幻想”只是存在于树已经有了之后,如何根据数组a(原始数组),来构造一棵树呢?一个简单的方法:文章源自JAVA秀-https://www.javaxiu.com/27787.html
每一次add之后都能保证树状数组是正确的,全加一遍后自然构建出一整棵树。文章源自JAVA秀-https://www.javaxiu.com/27787.html
时间复杂度对比
下面的暴力指的是开头提到的挨个相加
。文章源自JAVA秀-https://www.javaxiu.com/27787.html
求和文章源自JAVA秀-https://www.javaxiu.com/27787.html
暴力:
O(n)
(挨个相加,加n次)文章源自JAVA秀-https://www.javaxiu.com/27787.html树状数组:
O(log n)
(结构与二叉树相仿)文章源自JAVA秀-https://www.javaxiu.com/27787.html更改文章源自JAVA秀-https://www.javaxiu.com/27787.html
暴力:
O(1)
(改一次即可)文章源自JAVA秀-https://www.javaxiu.com/27787.html树状数组:
O(log n)
(需要改一串,但结构与二叉树相仿)文章源自JAVA秀-https://www.javaxiu.com/27787.html构造文章源自JAVA秀-https://www.javaxiu.com/27787.html
暴力:
O(n)
(当做是读入的复杂度)文章源自JAVA秀-https://www.javaxiu.com/27787.html树状数组:
O(n log n)
(做n次加法,每次加法为log n
)文章源自JAVA秀-https://www.javaxiu.com/27787.html
树状数组适合在:多次求和,多次修改,数据量大的场景下使用。文章源自JAVA秀-https://www.javaxiu.com/27787.html
如果无需支持修改,建议使用前缀和,构造
O(n)
,求和O(1)
文章源自JAVA秀-https://www.javaxiu.com/27787.html
代码
文章源自JAVA秀-https://www.javaxiu.com/27787.html
下面给出的是C++代码。文章源自JAVA秀-https://www.javaxiu.com/27787.html
BITMain为树状数组的使用案例,对应洛谷 树状数组https://www.luogu.com.cn/problem/P3374。文章源自JAVA秀-https://www.javaxiu.com/27787.html
//// Created by Cat-shao on 2021/2/9.//#include<cstdio>#include<cstring>usingnamespace std;constlonglong MAX_N =5000100;longlonglowbit(longlong x){return x &-x;}classBIT{public:longlong node[MAX_N], n;BIT(int _n){memset(node,0,sizeof(node)); n = _n;}longlongsum(int index){longlong sum =0;while(index >0){ sum += node[index]; index -=lowbit(index);}return sum;}voidadd(int index,longlong value){while(index <= n){ node[index]+= value; index +=lowbit(index);}}};intBITMain(){// https://www.luogu.com.cn/problem/P3374int n, m, op, x, y;longlong value;scanf("%d%d",&n,&m); BIT tree =BIT(n);for(int i =1; i <= n;++i){scanf("%lld",&value); tree.add(i, value);}for(int i =0; i < m;++i){scanf("%d%d%d",&op,&x,&y);if(op ==1){ tree.add(x, y);}elseif(op ==2){printf("%lld\n",(tree.sum(y)- tree.sum(x -1)));}}return0;}intmain(){BITMain();}
参考:胡凡《算法笔记》文章源自JAVA秀-https://www.javaxiu.com/27787.html
-End-
文章源自JAVA秀-https://www.javaxiu.com/27787.html文章源自JAVA秀-https://www.javaxiu.com/27787.html
文章源自JAVA秀-https://www.javaxiu.com/27787.html 如何给女朋友解释为什么Java 中"1000==1000"为false,而"100==100"为true?文章源自JAVA秀-https://www.javaxiu.com/27787.html文章源自JAVA秀-https://www.javaxiu.com/27787.html
文章源自JAVA秀-https://www.javaxiu.com/27787.html 雷军写代码水平如何?文章源自JAVA秀-https://www.javaxiu.com/27787.html文章源自JAVA秀-https://www.javaxiu.com/27787.html
文章源自JAVA秀-https://www.javaxiu.com/27787.html
史记 · 码农列传文章源自JAVA秀-https://www.javaxiu.com/27787.html
可乐记得加冰,爱我就要置顶
文章源自JAVA秀-https://www.javaxiu.com/27787.html
文章源自JAVA秀-https://www.javaxiu.com/27787.html
文章源自JAVA秀-https://www.javaxiu.com/27787.html
素质三连biubiubiu~
文章源自JAVA秀-https://www.javaxiu.com/27787.html

评论