利用树状数组解决几类问题

《利用树状数组解决几类问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、利用树状数组解决几类问题树状数组作为一种实现简单、应用较广的高级数据结构，在OI界的地位越来越重要，下面我来简单介绍一下树状数组和它的简单应用。一、树状数组简介树状数组(BinaryIndexedTrees，简称BIT)是一种特殊的数据结构，这种数据结构的时空复杂度和线段树相似，但是它的系数要小得多。它可以方便地查询出一段区间中的数字之和。其查询和修改的时间复杂度均为O(lbN),并且是一个在线的数据结构，可以随时修改并查询。我接下来用一道题目来介绍树状数组的几个基本操作。【引例】假设有一列数{Ai}（1<=i<=n），支持如下两种操作：1.

2、将Ak的值加D。（k，D是输入的数）2.输出（s，t都是输入的数，s<=t）这道题目用线段树很容易可以解决，我就不多说了，那么如何用树状数组来解决呢？我们新增一个数组C[]，其中C[i]=a[i-2k+1]+……+a[i](k为i在二进制形式下末尾0的个数)。根据定义我们可以得出一下这张表格：i二进制K1(1)20c[1]=a[1]2(10)21c[2]=a[1]+a[2]=c[1]+a[2]3(11)20c[3]=a[3]4(100)22c[4]=a[1]+a[2]+a[3]+a[4]=c[2]+c[3]+a[4]5(101)20c[5]=

3、a[5]6(110)21c[6]=a[5]+a[6]=c[5]+a[6]……在这里，我们会发现k值的求解会有一些难度，这就引出了树状数组的第一个操作：低位技术，也叫Lowbit(k)。对于Lowbit这里我提三种不同的写法（这三种形式是等价的，读者有兴趣可以去证明一下）：1.Lowbit(k)=kand(kor(k-1))2.Lowbit(k)=kandnot(k-1)3.Lowbit(x)=kand–k然后我来分析引例的树状数组解法，为了可以更好地理解这种方法，读者可以根据以下这幅图来加以理解。【操作2】修改操作：将Ak的值加D可以从C[i

4、]往根节点一路上溯，调整这条路上的所有C[]即可，这个操作的复杂度在最坏情况下就是树的高度即O(lbN)。 定理1：若A[k]所牵动的序列为C[p1]，C[p2]……C[pm]，则p1=k，而（li为pi在二进制中末尾０的个数）。 例如A[1]……A[8]中，a[3]添加x；p1=k=3p2=3+20=4p3=4+22=8p4=8+23=16>8由此得出，c[3]、c[4]、c[8]亦应该添加x。定理的证明如下：【引理】若A[k]所牵动的序列为C[p1]，C[p2]……C[pm]，且p1

5、二进制中末尾０的个数）。证明：若存在某个i有li≥li+1，则，，，即：(1)而由Li=Li+1、Pili的数（若出现Pi+x比pi+1更小，则x<2li，与x在二进制中的位数小于li相矛盾）。Pi+1=pi+2li，li+1≥li+1。由pi-2li+1≤K≤Pi可知，

6、Pi+1-2li+1+1≤Pi+2li–2*2li+1=Pi–2li+1≤K≤Pi≤Pi+1，故Pi与pi+1之间的递推关系式为Pi+1=Pi+2li【操作3】求数列的前n项和。只需找到n以前的所有最大子树，把其根节点的C加起来即可。不难发现，这些子树的数目是n在二进制时1的个数，或者说是把n展开成2的幂方和时的项数, 因此，求和操作的复杂度也是O(lbN)。根据c[k]=a[k-2l+1]+…+a[k](l为k在二进制数中末尾０的个数)，我们从k1=k出发，按：ki+1=ki-2lki（lki为ki在二进制数中末尾0的个数）递推k2，k3，

7、…，km(km+1=0)。由此得出S=c[k1]+c[k2]+c[k3]+…+c[km]相信看了这两个操作的理论部分，读者应该有了一定的理解，下面给出这两种操作和其他一些重要操作的Pascal代码。【操作1】低位技术：Lowbit(k)Lowbit(k)：即k在2进制数中从最低位开始连续0的位数的关于2的幂。代码FunctionLowbit(k:Longint):Longint;BeginLowbit:=kand–k;End;【操作2】修改操作：Modify(k,D)Modify(k,D)：对数组a[]中的第k个元素加上D。为了维护C[]数组

8、，我就必须要把C[]中所有“管”着a[k]的c[k]全部加上D，这样才能随时以O(lbN)的复杂度进行Sum(i)的操作。而"k:=k+Lowbit(k)"正是依次