树状数组培训课件.ppt

树状数组 先看一个例题: 数列操作: 给定一个初始值都为0的序列,动态地修改一些位置上的数字,加上一个数,减去一个数, 然后动态地提出问题,问题的形式是求出一段数字的和. 如果直接做的话,修改的复杂度是O(1),询问的复杂度是O(N),M次询问的复杂度是M*N.M,N的范围可以有100000以上 用树状数组!!! 怎么办 下图中的C数组就是树状数组,a数组是原数组 可以发现这些规律 C1=a1 C2=a1+a2 C3=a3 C4=a1+a2+a3+a4 C5=a5 C6=a5+a6 …… C8=a1+a2+a3+a4+a5+a6+a7+a8 …… C2^n=a1+a2+….+a2^n 对于序列a，我们设一个数组C定义C[i] = a[i – 2^k + 1] + … + a[i]，k为i在二进制下末尾0的个数。 K的计算可以这样: 2^k=x and (x xor (x-1)) 以6为例 (6)10=(0110)2 xor 6-1=(5)10=(0101)2 (0011)2 and (6)10=(0110)2 (0010)2 2^K(lowbit)求法 要想知道c[i]表示的是哪个区域的和,只要求出2^k(lowbit); 树状数组之所以高效简洁的原因就是能够利用位运算直接求出i对应的lowbit int lowbit(int i) { return i ( -i ); } 解释: 假设i为 则-i的 :1) 取反 2)+1 = 求和Sum 知道每个变量表示哪段的区间和之后就可以很快的求出前缀和了; 要求sum(i) = a[1]+...+a[i]; c[i]表示a[i-lowbit(i)+1]+...+a[i]; 还需要求a[1]+...+a[i-lowbit(i)]; 于是可以直接用一个循环求得sum,时间复杂度为O(logN) int getSum(int x) { int sum= 0; for (int i = x; i 0; i -= lowbit(i)) sum += c[i]; return sum; } 转化为子问题了! 循环的次数为x的二进制表示中1的个数 修改modify 修改了某个a[i],就需改动所有包含a[i]的c[j]; 从上图看就是要更改从改叶子节点到根节点路径上的所有c[j] 但是怎么求一个节点的父节点呢? Thinking...... 找父节点 增加虚构点,变成满二叉树!!! 每个节点的父亲就跟其右兄弟一样了; 而左右兄弟的管辖区域是一样的; 所以:i的父节点就是i+lowb(i); 修改modify void modify(int x,int delta) { for(int i = x; i=n; i+=lowbit(i)) c[i] += delta; } /*其中n为数组的长度 时间复杂度同样是O(logN)的*/ 树状数组的运用 对于刚才的一题,每次修改与询问都是对C数组做处理.空间复杂度为N,时间效率也有提高.编程复杂度更是降了不少. 优秀的算法！ 树状数组的运用 Poj2352 Star 天空中有一些星星，这些星星都在不同的位置，每个星星有个坐标。如果一个星星的左下方（包含正左和正下)有k颗星星，就说这颗星星是k级的. 比如，在下面的例图中，星星5是3级的（1，2，4在它左下）。星星2，4是1级的。例图中有1个0级，2个1级，1个2级，1个3级的星。 求出各个级别的星星的个数 题目分析： 算法有很多种,最实用的是树状数组 由于本题的数据输入是以y坐标的升序输入，所以，只需要比较x坐标即可 树状数组存储的是某一段范围内有多少个点，即求和. 小结 在很多的情况下,线段树都可以用树状数组实现.凡是能用树状数组的一定能用线段树.当题目不满足减法原则的时候,就只能用线段树,不能用树状数组.例如数列操作如果让我们求出一段数字中最大或者最小的数字,就不能用树状数组了. 树状数组的每个操作都是0(log(n))的复杂度. Thanks... ... Just do it: 简单: POJ 2299 Ultra-QuickSort POJ 2352 Stars POJ 1195 Mobile phones 中等 POJ 2155 Matrix POJ 3321 Apple Tree POJ 1990 MooFest 难题: POJ 2464 Brownie Points II * 按y值从小到大的格式输入，那么只要比较x在前