今天介绍一种特殊的数据结构-树状数组(binary index tree)，其巧妙利用了二进制的数学特性，对数组的索引下标的含义进行了特殊的定义，以方便对数组的任意区间内的元素进行求和。下面将简要向大家介绍一下其基本的原理。
为了求得一个数组中任意区间的元素的和，可以采用不同的方法，比较直接和朴素的方法是给出范围的区间，通过for循环去累加求和。但是这种方法求解的效率不高，如果数组的元素比较多，会影响程序的执行时间。树状数组通过巧妙的构造数组特定位置（下标）下的元素值的含义（通常为下标所映射的一定范围的元素的和），由于这种下标的巧妙映射，数组范围内任意区间的元素和都可以通过对应的较为少数的下标的元素的和去组成。而这种下标所对应数组元素范围的解析就是基于整数二进制编码的基本原理。下面将详细的通过示例进行介绍。
比如一个示例，求数组元素前15项的和。一般的数组每个索引下存放对应该位置的值，这样就需要做15次加法运算去求得所需的值。而这里我们的15的二进制表示为1111。如果不断的从右往左消除1，则可以分别由四个区间来组成，分别为（1110->1111]，(1100->1110],(1000,1100],(0000,1000]。而这几个区间可以分别看成是(14,15],(12,14],(8,12],(0,8]这几个区间的和，每个区间没有重叠（注意开闭区间的区别），假设数组的名称为treeindexarray，则treeindexarray[15]（1111）只表示15这个位置本身的值，treeindexarray[14](1110)表示13到14位置的和的值，treeindexarray[12]（1100）表示9到12位置的和的值，treeindexarray[8]代表1到8位置的和的值，这个对应范围和上述的区间是一致的。因此treeindexarray[8]+treeindexarray[12]+treeindexarray[14]+treeindexarray[15]这四个值相加的结果即为该数组的前15个元素之和，只需求4次加法即可。
更新数组中某个位置，其逻辑为该索引值为基础不断加上当前值的lowbit迭代直到索引越界。如数组中某个位置加或减去某个值，根据树状数组的定义，该索引之前的位置的值并不受影响。我们以简单的一个示例来进行说明，比如想把数组的第10个位置的值加上5（假设数组长度为31，32个元素但第索引为0处没有用到），则第10（二进制为1010）个位置本身要加上5，下一个加上5的位置为12（二进制为1100，根据上面的示例，其包含了9到12位置的值，因为10在内，所以也要加上5），再下一个需要加上5的位置的值为16（1100+lowbit(1100)，二进制为10000，该位置索引表示的是数组从1到16索引位置的和。由于16+lowbit(16)=32,查出了数组的边界，因此更新结束。比如求前面17（二进制为10001）个元素的和，则可以表示为（10000，10001],(00000,10000]两个区间的和。即为treeindexarray[17]+treeindexarray[16]，由于更新的第10个元素的位置已经在treeindexarray[16]中体现，所以最终的编码更新满足树状数组的逻辑定义。
在此进一步对lowbit的计算方式做一下说明。二进制编码的基本原理的基础上，求二进制数字最后一个为1的编码的位置的值得函数lowbit(x)，其计算方法利用到了计算机的二进制编码特性，在计算机中整数x的相反数-x的编码通常采用二进制补位方法（2’s Complement Representation，关于information encoding读者可以去了解更多的细节）。基于二进制补位表示法的机制，-x的二进制和x的二进制只在最右边编码为1的位置相同（其他位置均互补）。因此lowbit(x)= x&(-x)。
树状数组的应用场合可以参考引文中的开始的一个场景描述。后面有机会碰到更多的场景再在这里进行更新。
References
Leave a Reply