随笔-22  评论-7  文章-0  trackbacks-0

【引言】

          在解题过程中,我们有时需要维护一个数组的前缀和S[i]=A[1]+A[2]+...+A[i]。

          但是不难发现,如果我们修改了任意一个A[i],S[i]、S[i+1]...S[n]都会发生变化。

          可以说,每次修改A[i]后,调整前缀和S[]在最坏情况下会需要O(n)的时间。

          当n非常大时,程序会运行得非常缓慢。

          因此,这里我们引入“树状数组”,它的修改与求和都是O(logn)的,效率非常高。

【理论】

          为了对树状数组有个形 象的认识,我们先看下面这张图。


          如图所示,红色矩形表示的数组C[]就是树状数组。

          这里,C[i]表示A[i-2^k+1]到A[i]的和,而k则是i在二进制时末尾0的个数,

          或者说是i用2的幂方和表示时的最小指数。

         ( 当然,利用位运算,我们可以直接计算出2^k=i&(i^(i-1)) )

          同时,我们也不难发现,这个k就是该节点在树中的高度,因而这个树的高度不会超过logn。

          所以,当我们修改A[i]的值时,可以从C[i]往根节点一路上溯,调整这条路上的所有C[]即可,

          这个操作的复杂度在最坏情况下就是树的高度即O(logn)。  

          另外,对于求数列的前n项和,只需找到n以前的所有最大子树,把其根节点的C加起来即可。

          不难发现,这些子树的数目是n在二进制时1的个数,或者说是把n展开成2的幂方和时的项数,

          因此,求和操作的复杂度也是O(logn)。

          接着,我们考察这两种操作下标变化的规律:

          首先看修改操作:

          已知下标i,求其父节点的下标。
          我们可以考虑对树从逻辑上转化:

         如图,我们将子树向右对称翻折,虚拟出一些空白结点(图中白色),将原树转化成完全二叉树。

         有图可知,对于节点i,其父节点的下标与翻折出的空白节点下标相同。

         因而父节点下标 p=i+2^k  (2^k是i用2的幂方和展开式中的最小幂,即i为根节点子树的规模)

         即  p = i + i&(i^(i-1)) 。

         接着对于求和操作:

         因为每棵子树覆盖的范围都是2的幂,所以我们要求子树i的前一棵树,只需让i减去2的最小幂即可。

         即  p = i - i&(i^(i-1)) 。

        

         至此,我们已经比较详细的分析了树状数组的复杂度和原理。

         在最后,我们将给出一些树状数组的实现代码,希望读者能够仔细体会其中的细节。

【代码】

 求最小幂2^k:

int LowBit(int n)
{
    return n & (-n);
}
求前n项和:
int Sum(int nPos)
{
    int nSum = 0;
    while (nPos > 0)
    {
        nSum += C[nPos];
        nPos -= LowBit(nPos);
    }

    return nSum;
}
对某个元素进行加法操作:
void Modify(int nPos, int delta)
{
    while (nPos <= DATA_SIZE)
    {
        C[nPos] += delta;
        nPos += LowBit(nPos);
    }
}

以下代码是树状数组和普通加法的比较代码(VC6.0编译)
#include <iostream.h>
#include 
<stdlib.h> 
#include 
<malloc.h>
#include 
<windows.h>

#define DATA_SIZE 10000000

int A[DATA_SIZE];
int C[DATA_SIZE];

int LowBit(int n)
{
    
return n & (-n);
}



// Binary Indexed tree
int Sum1(int nPos)
{
    
int nSum = 0;
    
while (nPos > 0)
    
{
        nSum 
+= C[nPos];
        nPos 
-= LowBit(nPos);
    }


    
return nSum;
}


void Modify(int nPos, int delta)
{
    
while (nPos <= DATA_SIZE)
    
{
        C[nPos] 
+= delta;
        nPos 
+= LowBit(nPos);
    }

}


// Common Plus
int Sum2(int nPos)
{
    
int nSum = 0;
    
for ( int i=1; i<DATA_SIZE; i++ )
    
{
        nSum 
+= A[i];
    }


    
return nSum;
}



main()
{

    DWORD dwBegin,dwEnd;
    dwBegin 
= dwEnd = GetTickCount();

    
int nIndexChanged = 10;
    
int nData = 100;

    A[nIndexChanged] 
= nData;
    Modify(nIndexChanged,nData);

    
int nSum = Sum1(DATA_SIZE-1);
    cout
<<nSum<<endl;
    dwEnd 
= GetTickCount();
    
int nDiff = dwEnd-dwBegin;
    cout
<<"Time1:"<<dwEnd-dwBegin<<endl;
    cout
<<"---------------------"<<endl;

    dwBegin 
= dwEnd = GetTickCount();
    nSum 
= Sum2(DATA_SIZE-1);
    cout
<<nSum<<endl;
    dwEnd 
= GetTickCount();
    nDiff 
= dwEnd-dwBegin;
    cout
<<"Time2:"<<nDiff<<endl;
    cout
<<"---------------------"<<endl;
    
    
return 0;
}


posted on 2010-05-31 14:48 楚天清秋 阅读(478) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理