logging in or signing up tree Alohomora Download Post to : URL : Related Presentations : Share Add to Flag Embed Email Send to Blogs and Networks Add to Channel Uploaded from authorPOINTLite Insert YouTube videos in PowerPont slides with aS Desktop Copy embed code: (To copy code, click on the text box) Embed: URL: Thumbnail: WordPress Embed Customize Embed The presentation is successfully added In Your Favorites. Views: 32 Category: Entertainment License: All Rights Reserved Like it (0) Dislike it (0) Added: November 29, 2007 This Presentation is Public Favorites: 0 Presentation Description No description available. Comments Posting comment... Premium member Presentation Transcript 树状数组 : 树状数组 树状数组的运用: 树状数组的运用 首先我们得知道一个问题,那就是线段树得作用并不只是用来存储线段的,也可以存储点的值等等. 对于静态的线段树,空间上需要的数组有:当前结点的数据值,左儿子编号,右儿子编号.至少这么三个数组. 而在时间上虽然是NlogN的复杂度,但是系数很大. 实现起来的时候编程复杂度大,空间复杂度大,时间效率也不是很理想.树状数组的运用: 树状数组的运用 那么是否有更好的解决方法呢? 有! 那就是树状数组!树状数组的运用: 树状数组的运用 先看一个例题: 数列操作: 给定一个初始值都为0的序列,动态地修改一些位置上的数字,加上一个数,减去一个数,或者乘上一个数,然后动态地提出问题,问题的形式是求出一段数字的和.树状数组的运用: 树状数组的运用 如果直接做的话,修改的复杂度是O(1),询问的复杂度是O(N),M次询问的复杂度是M*N.M,N的范围可以有100000以上树状数组的运用: 树状数组的运用 用线段树可以这样解: 若要维护的序列范围是0..5,先构造下面的一棵线段树:树状数组的运用: 树状数组的运用 可以看出,这棵树的构造用二分便可以实现.复杂度是2*N. 每个结点用数组a来表示该结点所表示范围内的数据之和. 修改一个位置上数字的值,就是修改一个叶子结点的值,而当程序由叶子结点返回根节点的同时顺便修改掉路径上的结点的a数组的值. 对于询问的回答,可以直接查找i..j范围内的值,遇到分叉时就兵分两路,最后在合起来.也可以先找出0..i-1的值和0..j的值,两个值减一减就行了.后者的实际操作次数比前者小一些. 这样修改与维护的复杂度是logN.询问的复杂度也是logN,对于M次询问,复杂度是MlogN.树状数组的运用: 树状数组的运用 用树状数组!!! 然而不难发现,线段树的编程复杂度大,空间复杂度大,时间效率也不高.树状数组的运用: 树状数组的运用 下图中的C数组就是树状数组,a数组是原数组 先自己研究一下这个东西树状数组的运用: 树状数组的运用 可以发现这些规律 C1=a1 C2=a1+a2 C3=a3 C4=a1+a2+a3+a4 C5=a5 …… 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树状数组的运用: 树状数组的运用 function Lowbit(x: Integer): Integer; begin Lowbit := x and (x xor (x – 1)); end; 若要修改a[i]的值,则C数组的修改 是: Procedure change(k,delta:integer); Begin while k<=n do begin C[k]:=C[k]+delta; k:=k+lowbit(k); End; End;树状数组的运用: 树状数组的运用 若要求I..j的元素和的值,则求出 1..I-1的值和1..j的值. Function getsum(k:integer):integer; Var t:integer; Begin t:=0; while k>0 do begin t:=t+c[k]; k:=k-lowbit(k); end; getsum:=t; End;树状数组的运用: 树状数组的运用 对于刚才的一题,每次修改与询问都是对C数组做处理.空间复杂度有3N降为N,时间效率也有所提高.编程复杂度更是降了不少.树状数组的运用: 树状数组的运用 密码机(浙江2003省赛) 算法:树状数组或者线段树 与上题相比,所有的加号变成了xor. 由于xor满足交换律,结合律,所以可以和加法一样地做. 又A xor A=0,A xor 0=A.所以ADD和REMOVE是一样的操作.树状数组的运用: 树状数组的运用 Ural1028 Star 天空中有一些星星，这些星星都在不同的位置，每个星星有个坐标。 如果一个星星的左下方（包含正左和正下)有k颗星星，就说这颗星星是k级的.比如，在下面的例图中，星星5是3级的（1，2，4在它左下）。 星星2，4是1级的。例图中有1个0级，2个1级，1个2级，1个3级的星。 求出各个级别的星星的个数树状数组的运用: 树状数组的运用 算法有很多种,最实用的是树状数组 先对X排序,然后就是查找每个坐标前面的坐标种Y比他小的又多少个.这需要树状数组. 树状数组存储的是某一段范围内有多少个点.小结: 小结 在很多的情况下,线段树都可以用树状数组实现.凡是能用树状数组的一定能用线段树.当题目不满足减法原则的时候,就只能用线段树,不能用树状数组.例如数列操作如果让我们求出一段数字中最大或者最小的数字,就不能用树状数组了. You do not have the permission to view this presentation. In order to view it, please contact the author of the presentation.
tree Alohomora Download Post to : URL : Related Presentations : Share Add to Flag Embed Email Send to Blogs and Networks Add to Channel Uploaded from authorPOINTLite Insert YouTube videos in PowerPont slides with aS Desktop Copy embed code: (To copy code, click on the text box) Embed: URL: Thumbnail: WordPress Embed Customize Embed The presentation is successfully added In Your Favorites. Views: 32 Category: Entertainment License: All Rights Reserved Like it (0) Dislike it (0) Added: November 29, 2007 This Presentation is Public Favorites: 0 Presentation Description No description available. Comments Posting comment... Premium member Presentation Transcript 树状数组 : 树状数组 树状数组的运用: 树状数组的运用 首先我们得知道一个问题,那就是线段树得作用并不只是用来存储线段的,也可以存储点的值等等. 对于静态的线段树,空间上需要的数组有:当前结点的数据值,左儿子编号,右儿子编号.至少这么三个数组. 而在时间上虽然是NlogN的复杂度,但是系数很大. 实现起来的时候编程复杂度大,空间复杂度大,时间效率也不是很理想.树状数组的运用: 树状数组的运用 那么是否有更好的解决方法呢? 有! 那就是树状数组!树状数组的运用: 树状数组的运用 先看一个例题: 数列操作: 给定一个初始值都为0的序列,动态地修改一些位置上的数字,加上一个数,减去一个数,或者乘上一个数,然后动态地提出问题,问题的形式是求出一段数字的和.树状数组的运用: 树状数组的运用 如果直接做的话,修改的复杂度是O(1),询问的复杂度是O(N),M次询问的复杂度是M*N.M,N的范围可以有100000以上树状数组的运用: 树状数组的运用 用线段树可以这样解: 若要维护的序列范围是0..5,先构造下面的一棵线段树:树状数组的运用: 树状数组的运用 可以看出,这棵树的构造用二分便可以实现.复杂度是2*N. 每个结点用数组a来表示该结点所表示范围内的数据之和. 修改一个位置上数字的值,就是修改一个叶子结点的值,而当程序由叶子结点返回根节点的同时顺便修改掉路径上的结点的a数组的值. 对于询问的回答,可以直接查找i..j范围内的值,遇到分叉时就兵分两路,最后在合起来.也可以先找出0..i-1的值和0..j的值,两个值减一减就行了.后者的实际操作次数比前者小一些. 这样修改与维护的复杂度是logN.询问的复杂度也是logN,对于M次询问,复杂度是MlogN.树状数组的运用: 树状数组的运用 用树状数组!!! 然而不难发现,线段树的编程复杂度大,空间复杂度大,时间效率也不高.树状数组的运用: 树状数组的运用 下图中的C数组就是树状数组,a数组是原数组 先自己研究一下这个东西树状数组的运用: 树状数组的运用 可以发现这些规律 C1=a1 C2=a1+a2 C3=a3 C4=a1+a2+a3+a4 C5=a5 …… 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树状数组的运用: 树状数组的运用 function Lowbit(x: Integer): Integer; begin Lowbit := x and (x xor (x – 1)); end; 若要修改a[i]的值,则C数组的修改 是: Procedure change(k,delta:integer); Begin while k<=n do begin C[k]:=C[k]+delta; k:=k+lowbit(k); End; End;树状数组的运用: 树状数组的运用 若要求I..j的元素和的值,则求出 1..I-1的值和1..j的值. Function getsum(k:integer):integer; Var t:integer; Begin t:=0; while k>0 do begin t:=t+c[k]; k:=k-lowbit(k); end; getsum:=t; End;树状数组的运用: 树状数组的运用 对于刚才的一题,每次修改与询问都是对C数组做处理.空间复杂度有3N降为N,时间效率也有所提高.编程复杂度更是降了不少.树状数组的运用: 树状数组的运用 密码机(浙江2003省赛) 算法:树状数组或者线段树 与上题相比,所有的加号变成了xor. 由于xor满足交换律,结合律,所以可以和加法一样地做. 又A xor A=0,A xor 0=A.所以ADD和REMOVE是一样的操作.树状数组的运用: 树状数组的运用 Ural1028 Star 天空中有一些星星，这些星星都在不同的位置，每个星星有个坐标。 如果一个星星的左下方（包含正左和正下)有k颗星星，就说这颗星星是k级的.比如，在下面的例图中，星星5是3级的（1，2，4在它左下）。 星星2，4是1级的。例图中有1个0级，2个1级，1个2级，1个3级的星。 求出各个级别的星星的个数树状数组的运用: 树状数组的运用 算法有很多种,最实用的是树状数组 先对X排序,然后就是查找每个坐标前面的坐标种Y比他小的又多少个.这需要树状数组. 树状数组存储的是某一段范围内有多少个点.小结: 小结 在很多的情况下,线段树都可以用树状数组实现.凡是能用树状数组的一定能用线段树.当题目不满足减法原则的时候,就只能用线段树,不能用树状数组.例如数列操作如果让我们求出一段数字中最大或者最小的数字,就不能用树状数组了.