树状数组及其应用双语版解读.ppt

树状数组及其应用 引例 【题目描述】 输入一个数列A1,A2….An(1=N=100000)，在数列上进行M(1=M=100000)次操作，操作有以下两种： 格式为C I X，其中C为字符“C”，I和X(1=I=N,|X|=10000)都是整数，表示把把a[I]改为X 格式为Q L R，其中Q为字符“Q”，L和R表示询问区间为[L,R](1=L=R=N)，表示询问A[L]+…+A[R]的值。 【输入】 第一行输入N(1=N=100000)，表述数列的长度，接下来N行，每行一个整数(绝对值不超过10000)依次输入每个数；接下来输入一个整数M(1=M=100000)，表示操作数量，接下来M行，每行为C I X或者Q L R。 【输出】 对于每个Q L R 的操作输出答案。 如果直接用数组模拟，那么修改是O(1),查询是O(n),如果维护另一个数组b[i]，表示a[1]到a[i]的和，那么修改是O(n),查询时O(1)。 一个程序的时间复杂度取决于其中最大的时间复杂度。 树状数组的目的就是平摊修改和查询的时间，使复杂度由O(n)降到O(lgn)。 树状数组是一种数据结构，这种结构能让我们的程序变得高效，数据结构大多数时候是为了优化算法而用的。 树状数组对于原数组a维护另一个数组c，c[i]表示sum(a[j]),i-lowbit(i)+1=j=i,其中lowbit(i)表示取出i二进制表示中最右边的1。 例如lowbit(6)=lowbit(110)2=(10)2=2 所以 c[6]=a[5]+a[6]; lowbit(4)=lowbit(100)2=(100)2=4 c[4]=a[1]+a[2]+a[3]+a[4] lowbit[5]=lowbit(101) 2 =(1) 2=1; c[5]=a[5] 其比较简单的算法为 lowbit(i)=i (-i) 或i (i ^ (i-1)) 结论 1、节点i的父亲节点为i+lowbit(i) 2、节点i的最近不相交前驱为i-lowbit(i) 3、若需改变a[i]，则c[i]、c[i+lowbit(i)]、c[i+lowbit(i)+lowbit(i+lowbit(i)]……一直加到上限，就是需要改变的c数组中的元素。 4、若需查询s[i]，则c[i]、c[i-lowbit(i)]、c[i-lowbit(i)-lowbit(i-lowbit(i))]……就是需要累加的c数组中的元素。 5、以上的修改和查询都是log2(n)级别的。 Procedure add(k,delt); Begin while k=limit do begin C[k]:=C[k]+delta; k:=k+lowbit(k); End; End; Function getsum(k:integer):integer; Var t:integer; Begin t:=0; while k0 do begin t:=t+c[k]; k:=k-lowbit(k); end; getsum:=t; End; 在实际应用中，通常不需要保存原数组a，只保存数组c即可。因此，树状数组几乎不需要附加空间。 通过上面的学习可以看出：树状数组所能支持的操作是修改点值、查询区间和。 与线段树和其他数据结构相比，树状数组代码简单，常数小，在其能解决范围内或经过转化使用树状数组，可以极大的降低编程复杂度，使代码清晰，简洁 例题、Stars(ural 1028) 题目大意 平面中有N个点，对于 每个点(x,y)，要求输 出在其左下方（包括正 左正下）点的个数。 N=100000; x,y=maxlongint 枚举？ 代码简单，时间复杂度达到O(n2) 有没有代码简单、时间复杂度低的方法？ 此题有效的算法很多，树状数组可以简洁快速的解决此问题。 如何构建树状数组？ 如何处理巨大的(x,y)？ 如何处理“左下方”？ 首先，离散化y坐标，然后按x坐标从小到大 排序，x相同则y坐标由小到大，从左到右扫描每个点，这样可以保证已经插入树状数组的点都在左侧或正下侧。 我们只需寻找有 多少点位于当前点下 方，很容易想到树状 数组。处理完当前点 后，将其按y坐标插入 树状数组，即让a[y]加1 此题是树状数组的经典应用 首先离散化坐标使数据范围减小，为使用树状数组创造了条件 按横坐标排序，使得原题中“左下方”两个条件限制转化为“下方”这一单一限制 可以轻松运用树状数组解决 现在，我们将树状数组推广到二维 先看一道神奇的题目 2、Superbrother打鼹鼠(vijos 1512)