漫画:什么是树状数组?
共 370字,需浏览 1分钟
·
2020-08-05 14:47
![](https://filescdn.proginn.com/997cd59301cad9eae48be6317a8dc2db/687cca78383d6bae38401d8665c35760.webp)
![](https://filescdn.proginn.com/ab2c37395bebb8787ed0b20718ff0d95/7c6555f499a8f4d303a5274be93607ff.webp)
我们学习数据结构的目的在于将我们的算法变得更快。由 Peter M. Fenwick 提出的树状数组 BIT 结构就是一个优秀的数据结构,BIT 全称 Binary Indexed Trees 结构,而不是所说的比特奥。Peter M. Fenwick 首次使用此结构进行数据压缩。在算法竞赛中,通常用于存储频率和处理累积频率表。
首先考虑一个简单的问题。
给定一个数组 arr[0 ... n-1]
,如何实现下面两个操作:
计算前 i 个元素的累加和; 将数组中下标为 i 的元素的值更新为 x, arr[i] = x
,其中0 <= i <= n-1
一个简单的方法就是遍历 0 到 i - 1 的元素并计算出累加和即可 ;然后更新操作 arr[i] = x
就可以直接进行,也就说可以对数组 arr[]
直接进行修改.
// 计算前 i 个元素的累加和
public int getSum(int arr[], int i){
int sum = 0;
for(int j = 0; j < i; j++){
sum += arr[j];
}
return sum;
}
这种方式第一个操作,也就是计算累加和的时间复杂度为 ,更新操作的时间复杂度为 ;
另外一种方式就是创建一个大小为 n 的新数组,并且在新数组的第 i 个位置保存前 i 个元素的累加和。此时查找给定范围内的累加和就可以在 的时间内完成,但是更新操作将花费 的时间,这对于大量的查询操作,而更新操作比较少的问题很实用。
// 更新数组 arr[i] = x 之后
// 需要对存储累加和的数组 new_arr 进行的修改。
void updateSum(int arr[], int i, int x){
arr[i] = x;
for(int j = i; j < new_arr.length; j++){
new_arr[j] = new_arr[j-1] + arr[j];
}
}
也就说,要实现上面提到的两个操作,要么查找为 ,更新操作为 ;要么使用额外的空间,将查找操作降为 ,但是更新操作变为了 .
树状数组
那么是否可以将查找和更新操作同时降低到 呢?
一个就是以后会讲到的线段树(Segment Tree),另外一个就是树状数组 (Binary Indexed Tree),两者均可以将上面所提到的查找和更新操作的时间复杂度降到 。但是与线段树相比,树状数组的效率更高,并且易于实现。
树状数组表示为 BITree[]
;树状数组的每个节点存储输入数组中某些元素的和;树状数组的大小等于输入数组的大小,记作 n 。为了便于实现,BITree[]
使用 n+1 的大小。
首先,我们给出一个数组 arr[]
:
![](https://filescdn.proginn.com/22cf689567a0550504a5f3937e48f8f9/48df5d6076466b89920aec86dd47b130.webp)
然后直接直观地看一下针对这个数组 arr[]
的树状数组:
![](https://filescdn.proginn.com/0e4bb987e3c4799f47976b6d96d9ca99/6630957059ad03dfc28f150a6470f347.webp)
事实上这棵树并不存在,树状数组依然只是下面的一个数组而已:
![](https://filescdn.proginn.com/8d411efe6b1dcdc5993f8c3dda5fffd0/045872358ef1170b4cc0a61479b38d6c.webp)
现在的问题是如何从原始数组 arr[]
得出树状数组 BITree[]
呢?
答案很简单:
首先将树状数组 BITree[]
的所有元素初始化为 0;调用 updateBITree()
函数更新BITree[]
数组即可。
所以关键就是实现 updateBITree()
函数啦!
实现(敲代码)不是关键,重要的是理解为什么!
我们先来细致地看一趟 updateBITree()
函数的执行过程:
第一步:index = 1
,将 BITree[1] = BITree[1] + arr[0]
:
![](https://filescdn.proginn.com/25b243b9015ce73c31cc86b323571618/092d203b21742332f102e23c3f79df45.webp)
第二步:更新 index = index + index & (-index) = 1 + 1 = 2
,这里你可能一头雾水,没关系,这篇文章最后没有让你彻底明白树状数组,你大可喷我!我暂且不解释它的含义和作用,我们仅仅解释一下 index & (-index)
表示什么。index & (-index)
表示将 index
所代表的值转化为二进制之后,从右向左数,第一个 1 的位置,例如 6 & (-6)
,6 的二进制为 110 ,从右向左数,第一个 1 的位置是 2 ,那么 6 & (-6) = 2
。当然这是二进制运算之中取最后一个 1 的小诀窍,下面是的,以一个32位的机器为例:
![](https://filescdn.proginn.com/3625ed70c0657fe9c52b448806d0cc75/257916c11ffd8bb3d4664ff78cd60161.webp)
这里如果有问题,大家可以看一下 剑指 offer 面试题精选图解 15 . 二进制中1的个数 这篇文章,然后复习一下原码、反码和补码接着看。
第三步:index = 2
,将 BITree[2] = BITree[2] + arr[0]
:
![](https://filescdn.proginn.com/2df8e5da14dab2f3cdd663d5dfc103ad/f24f4664b03bae71458d47afcfdad639.webp)
第四步:更新 index = index + index & (-index) = 2 + 2 = 4
第五步:index = 4
,将 BITree[4] = BITree[4] + arr[0]
:
![](https://filescdn.proginn.com/a4b5f54ff7cbeea4989acfab2723cdc0/aab4a3db971a350be2b3c48302d61971.webp)
第六步:更新 index = index + index & (-index) = 4 + 4 = 8
第七步:index = 8
,将 BITree[8] = BITree[8] + arr[0]
:
![](https://filescdn.proginn.com/470f09b39f7a0bad3919d1019f6869b7/643a0b6e1a81eef8a4c31f694d804eb8.webp)
第八步:更新 index = index + index & (-index) = 8 + 8 = 16
,16 > 12 ,已经超出了树状数组 BITree[] 的下标,一趟 updateBITree()
函数的执行结束啦!知道你没啥感觉更是没有体会到树状数组的妙用(我刚开始也是,说实话,笨笨的大禹看了好几天)。
但是当你将所有的步骤都都走完之后,你就会感觉不一样啦!
![](https://filescdn.proginn.com/c1536ccbac0f85d4da06be88e9e44f1e/ae1cc871b8d984001607dff57488f91b.webp)
图中没有填充的单元格都表示 0,第 1 趟 updateBITree()
函数确定了 BITree[1]
的值,第 2 趟 updateBITree()
函数确定了 BITree[2]
的值,以此类推,第 12 趟 updateBITree()
函数确定了 BITree[12]
的值,也就是结果 12 (12就是数组 arr[]
的大小)趟更新,我们得到了我们的主角 BITree[]
树状数组:
![](https://filescdn.proginn.com/8d411efe6b1dcdc5993f8c3dda5fffd0/045872358ef1170b4cc0a61479b38d6c.webp)
也就是,我们完成了从数组 arr[]
到 BITree[] 的过渡。
下面我要告诉你的才是树状数组的关键和核心奥!
树状数组的关键不是 BITree[] ,而是 下标 。
假设现在的原始数组 arr[]
的大小 n = 16
,我们看下标 1 到 16 到底如何成为树状数组的关键所在的。
![](https://filescdn.proginn.com/d4b7e61d2ef9b3846ee68075ef53a102/083115e2fb0dc5d7ffeba7c24715e738.webp)
对于上面的每一个 index
, 均计算 index & (-index)
的值,比如 10,可以计算得到 10 & (-10) = 2
,实在不会也没关系,就把 10 转化为二进制 1010
,然后从右向左数数,碰到的第一个 1 的位置就是 2 (其他数字的计算都是一样的过程,就不过多说明)。
![](https://filescdn.proginn.com/59cfac1f2716523ce230dedcbf7fbab6/8b149b34ed2f7c66a1aeb606da3ec4f0.webp)
而这个 index & (-index)
所对应的值有何意义呢?
答案,index & (-index)
表示一个范围,千篇一律的叫法叫做 Lowbit(index)。
以 index & (-index)
中的第一个 1 为例,它表示将数组 arr[]
中当前位置向前累加 1 个数字,作为 BITree[index]
的值,即 BITree[1] = 2
.
![](https://filescdn.proginn.com/18b21377560caa392350e6473e3a8a29/734d4b99e36b0cde76f538c99d984d0e.webp)
那么 BITree[] 数组中的值 30 的由来就更好解释了,就是从当前元素 9 向前累加 4 个元素(包含自身),即 9 + 8 + 7 + 6 = 30
![](https://filescdn.proginn.com/24300e0e1853a38b951386e3f58251f8/fd6a6194155d8fa973fe758b603f7f8b.webp)
对于 index & (-index)
中的其他元素的解释是同样的道理。但是 index & (-index)
所表示的数组你以为就这样简单吗?若真是如此,估计我就不讲了。
就一棵树而言,必定有父子之分,那么树状数组是如何体现父子关系的呢?
BITree[y]
是BITree[x]
的父结点,当且仅当 y 可以通过从 x 的二进制表示中删除最后一个位置的 1 (也就是从右向左第一个) 来获得,即y = x - (x & (-x))
有了这样的父子关系,仅使用 index & (-index)
就可以直观地构建出我们期待已久的树状数组中所谓的树。
已知 index
和 index & (-index)
,计算两者之差简直轻而易举:
![](https://filescdn.proginn.com/0ba9d76b59b3e03544494932f655f4b6/5cb41388fa49aab6adffebeb4e16e964.webp)
那么构建一颗树还难吗?一点儿都不。
比如 y 等于 0 ,视线向上找到对应的 index,分别为 1、2,4、8、16,也就是说,0是 1、2、4、8、16 的父结点;
同理,2 是 3 的父结点、4 是 5 和 6 的父结点、6 是 7 的父结点、8 是 9 和 10 的父结点,10 是 11 和12 的父结点、12 是 13 和 14 的父结点,14 是 15 的父结点。
就得到了下图:
![](https://filescdn.proginn.com/16c92b48ea347de810c7bf6375b1cf07/e430fdff63989307819a379a45904363.webp)
这棵树的得出与原数组 arr[]
本身没有关系,而仅仅与下标 index 有关。而我们最开始所看到的树同样如此(只不过树中结点的真正的值是我们所计算出的 BITree[index]
:
![](https://filescdn.proginn.com/0e4bb987e3c4799f47976b6d96d9ca99/6630957059ad03dfc28f150a6470f347.webp)
树状数组的几大特点:
BITree[0] 是一个虚拟结点,同时也是我们所看到的根结点 BITree[y]
是BITree[x]
的父结点,当且仅当 y 可以通过从 x 的二进制表示中删除最后一个位置的 1 (也就是从右向左第一个) 来获得,即y = x - (x & (-x))
BITree[y]
的孩子结点BITree[x]
存储的是数组arr[]
中下标从 y (包含) 到 x (不包含) 的累加和,即arr[y,...,x)
,注意括号是不包含 x;
关于这个第三条可能需要稍微解释一下:
![](https://filescdn.proginn.com/b724b74882a608d18db04c3b32df39f8/772f38c24df9e732367d6584b9ec8fe2.webp)
BITree[8]
的孩子结点 BITree[12]
的值等于 30 ,表示数组 arr[] 中下标从 8 到 12(不包含 12)的元素的累加和,即 BITree[12] = 30 = arr[8,...,12) = 6 + 7 + 8 + 9
。
其实这里就和之前我们介绍的 index & (-index)
所表示含义不谋而合。
是不是有点儿清晰呢?很快你就会看到一句话概括上面所讲的所有内容。
回到我们最开始的两个问题。
如何根据 BITree[]
树状数组,获取数组 arr[]
中前 i 个元素的累加和?
这里更关键奥!!!
我们都知道,任何一个正整数都可以被表示为 2 的次幂和,比如 11 可以表示为 8 + 2 + 1. BITree的每个节点都存储 n 个元素的总和,其中 n 是 2 的次幂。比如前 11 个元素的累加和可以通过对原数组 arr[]
中最后 1 个元素(第11个元素)、向前两个元素(第 9 和 10 号元素)和 前 8 个元素 (从 1 到 8 的)的元素之和求得。
![](https://filescdn.proginn.com/208493051b1c266bb35cb7c5adb53d58/9c96eb854a8b9606a460cd690e652458.webp)
对照上图,来理解文字描述就更清晰了,我们求前 11 个元素的累加和,可以将其分解为 2 的次幂之和,即 8 + 2 + 1,也就是前 8 个元素的累加和(1 到 8),紧挨着的 2 个元素(9 和 10),和最后 1个元素 (11)三者的和。
如果从树状数组的角度来看,BITree[8] = 21
表示前 8 个元素的累加和,BITree[10] = 13
表示 6 和 7 的和(这里解释一下, 表示的就是两个数的和), BITree[11] = 8
表示一个 8 (,表示 1 个数的和) 。所以前 11 个元素的累加和等于 BITree[8] + BITree[10] + BITree[11] = 21 + 13 + 8 = 42
。
如果再从更直观的树上看,计算前 11 个元素的累加和,从叶子结点 11 开始,找到 11 的父结点 10,然后找到 10 的父结点 8 ,8 的父结点为 0 ,然后将路径上的值都加起来,就是前 11 个元素的累加和。
不难写出下面计算累加和的代码:
int getSum(int index)
{
int sum = 0; // 累加和
// BITree[] 的下标比 arr[] 大 1
index = index + 1;
// 遍历 BITree[index] 的祖先结点
while(index>0)
{
// 将当前 BITree 的值加到 sum
sum += BITree[index];
// 将 index 指向 index 的父结点
index = index - index & (-index);
}
return sum;
}
代码很清晰,就是从给定的 index 遍历 index 的所有的祖先结点,并将遍历到的 BITree[index]
的值加起来即可。
如何将数组中下标为 i 的元素的值更新为 x,且在 O(logn) 的时间内更新树状数组 BITree[]
?
虽然关于这个问题在最开始的时候已有阐述,但我们再以一个例子介绍一遍!
现在将 arr[3] = arr[3] + 6
,时间复杂度为 :
![](https://filescdn.proginn.com/2227eeed726c5c15752a1b8b42f234d7/204061c95e90c5a93158df5d793937f1.webp)
然后更新树状数组 BITree[]
,时间复杂度为 :
index = 4
,将 BITree[index] += val
,即 BITree[4] = 7 + 6 = 13
.
![](https://filescdn.proginn.com/87258f38d7b5970fc800e4aa8e893fd1/24f38d1ab7309c564f905a995b9e71fc.webp)
更新 index
,index = index + index & (-index) = 4 + 4 = 8
;
更新 BITree[index]
,即 BITree[8] = 21 + 6 = 27
:
![](https://filescdn.proginn.com/8b1bac408a5f9c0502a77f37c0783554/0ae60a98aeb6e99c5b23dd952e72cfaa.webp)
更新 index
,index = index + index & (-index) = 8 + 8 = 16 > 12
,更新过程结束。
代码也相当简单:
public static void updateBIT(int n, int index, int val)
{
// BITree[] 的下标比 arr[] 大 1
index = index + 1;
// 遍历所有的祖先,并加上 'val'
while(index <= n)
{
// BIT Tree 的当前结点加上 'val'
BITree[index] += val;
// 更新 index
index += index & (-index);
}
}
能否将树状数组扩展到以 的时间复杂度计算区间和呢?
答案是肯定的,rangSum(l,r) = getSum(r) - getSum(l - 1)
.
复杂度分析
任何一个正整数 n 的二进制表示中置位数的个数为 量级,置位数就是一个整数二进制表示中 1 的数目。因此,getSum()
和 updateBIT()
两个操作至多遍历 个结点。
初始构造树状数组 BITree[]
的时间复杂度为 ,构造 BITree[]
树状数组会调用 updateBIT()
函数 n 次。
完整的实现代码
import java.util.*;
import java.lang.*;
import java.io.*;
class BinaryIndexedTree
{
final static int MAX = 100;
static int BITree[] = new int[MAX];
int getSum(int index)
{
int sum = 0;
index = index + 1;
while(index>0)
{
sum += BITree[index];
index -= index & (-index);
}
return sum;
}
public static void updateBIT(int n, int index,
int val)
{
index = index + 1;
while(index <= n)
{
BITree[index] += val;
index += index & (-index);
}
}
void printBITree(int arr[], int n) {
for(int i = 0; i < n; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
void constructBITree(int arr[], int n)
{
for(int i=1; i<=n; i++)
BITree[i] = 0;
for(int i = 0; i < n; i++) {
updateBIT(n, i, arr[i]);
printBITree(BITree,n+1);
}
}
public static void main(String args[])
{
int arr[] = {2, 1, 1, 3, 2, 3, 4, 5, 6, 7, 8, 9};
int n = arr.length;
BinaryIndexedTree tree = new BinaryIndexedTree();
// 从给定的数组 arr[], 构造 BITree[]
tree.constructBITree(arr, n);
System.out.println("arr[0..5] = " + tree.getSum(5));
// 测试更新操作
arr[3] += 6;
// arr[3] 的改变,更新 BITree[]
updateBIT(n, 3, 6);
System.out.println("arr[0..5] = " + tree.getSum(5));
}
}
来个直击灵魂的三连!