数据结构之 树状数组 （Binary Indexed Tree ）北京理工大学ACM集训队陈翔问题的引入：给定n个数，a1.an。每次我们可能有两种操作：（1）求出ai.aj的和；（2）给ax的值加上一个值val。n的规模如果比较大（约100000）该如何高效的实现？树状数组看图形回答问题：（1）C数组是用于求和的，想想，每个Ci求的是哪几个数的和？（2）整个图形像是棵树，每个节点会有几个孩子？（3）每个孩子节点向上的，直接父亲节点是哪个节点？提示：看每个数字的二进制码 ！大家一起来解答：（1）Ci记录了哪些数的和？ 0001 C1=a1 0010 C2=a1+a2 0011 C3=a3 0100 C4=a1+a2+a3+a4 0101 C5=a5 0110 C6=a5+a6 0111 C7=a7 1000 C8=a1+a2+a3+a4+a5+a6+a7+a8 结论：第x个数，记录了x for (; x0; x-=x return sum; 有时亦用: lowbit(x)表示x jaj x-=lowbit(x) for (y=Y; y0; y-=lowbit(y) sum+=Cxy; return sum; 树状数组二分：树状数组以其独特的结构形成了二分的条件。以一道题引入：POJ 2182给定n个随机排列的数，若是知道每个数前面有多少比自己小的数，请问，该排列的形式是怎样的？例：5 0 1 2 1 0ans：2 4 5 3 1倒着向前处理：把原来全为0的C数组，在1.n的每一位走增加1标记。然后在数组数组里查询第ai+1个1int find(int k) /正向建立时找到第k个1的位置 int ans=-1,bit,pos,sum; /pos目前处于的位置 pos=sum=0; /sum目前位置之前的所有的和 for (bit=1=1) if (pos+bit=k的最小的位置 return ans; 树状数组的其他用处：其实树状数组还可以进行区间动态查找最大，最小值的，代码短而精悍，效率也较高。有兴趣的话，大家课下可以再去探索探索！最后留下习题：POJ 2299POJ 2352POJ 2481POJ 3067POJ 1195POJ 2029POJ 2182HDU 2852