树状数组
第 01 讲 什么是树状数组？
树状数组用来求区间元素和，求一次区间元素和的时间效率为 O(logn)。
有些同学会觉得很奇怪。用一个数组 S[i]保存序列 A[]的前 i 个元素和，那么求区间 i,j 的元素和不就为
S[j]-S[i-1]，那么时间效率为 O(1)，岂不是更快？
但是，如果题目的 A[]会改变呢？例如：
我们来定义下列问题：我们有 n 个盒子。可能的操作为
1.向盒子 k 添加石块
2.查询从盒子 i 到盒子 j 总的石块数
自然的解法带有对操作 1 为 O(1)而对操作 2 为 O(n)的时间复杂度。但是用树状数组，对操作 1 和 2 的时间
复杂度都为 O(logn)。
第 02 讲 图解树状数组 C[]
现在来说明下树状数组是什么东西？假设序列为 A[1]~A[8]
网络上面都有这个图，但是我将这个图做了 2 点改进。
（1）图中有一棵满二叉树，满二叉树的每一个结点对应 A[]中的一个元素。
（2）C[i]为 A[i]对应的那一列的最高的节点。
现在告诉你：序列 C[]就是树状数组。
那么 C[]如何求得？
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];
以上只是枚举了所有的情况，那么推广到一般情况，得到一个 C[i]的抽象定义：
因为 A[]中的每个元素对应满二叉树的每个叶子，所以我们干脆把 A[]中的每个元素当成叶子，那么：
C[i]=C[i]的所有叶子的和。
现在不得不引出关于二进制的一个规律：
先仔细看下图：
剩余13页未读，继续阅读
资源评论
