C++实用数据结构：二叉索引树

C++实用数据结构：二叉索引树

看下面这个问题（动态连续和查询）：

有一个数组A（长度为n），要求进行两种操作：

add(i,x)：让Ai增大x；

query(a,b)：询问Aa+Aa+1+...+Ab的和；

若进行模拟，则每次query操作的最坏的时间复杂度为O(n)，在n较大时速度较慢。用前缀和也不能提高效率（每次add操作最坏为O(n)）。有一种数据结构，可以在O(n)时间里初始化，用O(logn)的速度执行add操作或查询前缀和，从而执行query操作。

首先，我们来介绍“lowbit”。对于一个数x，lowbit(x)是x的二进制里最右面的1所代表的数字，例如lowbit(20)=4,因为20的二进制为10100，最右面的1代表4。怎样计算lowbit呢？很简单，lowbit(x)=x&-x。这是因为负数是用补码保存的，-x就相当于(~x)+1。例（用8位计算）：

20=(00010100)

-20=(11101100)

现在我们来介绍二叉索引树。二叉索引树在程序中也是用数组来保存的。

（画得难看请见谅）

图中，深灰色方块代表树中的结点（结点0为虚拟结点），灰色线段代表树中的边。这些边并不需要显式保存；对于一个节点x，若它是父结点的左子结点，则父结点编号为x-lowbit(x)，否则为x+lowbit(x)。图中的每个结点左侧都有一个白色长条（包括它自己），如结点4的长条为1~4，节点3的长条为3~3。不难发现，结点x的长条为(x-lowbit(x)+1)~x。

然后，我们用一个数组S储存每个结点的白色长条内的所有数的和。例如，S4=A1+A2+A3+A4。这样，就可以使用一个辅助的前缀和数组,在O(n)时间内从左到右初始化S数组。代码如下：

int n;
int S[maxn],A[mxan],S1[maxn];
int begin()
{
    memset(S1,0,sizeof(S1));
    for(int i=1;i<=n;i++)
    {
        S1[i]=S1[i-1]+A[i];
        S[i]=S1[i]-S1[i-lowbit(i)];
    }
}

最后让我们来实现add操作和查询操作。对于某个add操作的结点i，它的修改会影响到那些结点呢？很显然，在它下面的结点（lowbit比它小）不会受到影响，在它左边的结点也不会受到影响，所以只需要考虑在它右边且lowbit比它大的第一个结点，这个结点的白色长条一定覆盖x。很显然，这个结点的编号为i+lowbit(i)。

接下来，x结点不需要考虑了，让我们来考虑i+lowbit(i)结点。与上面一样，只需要考虑在它右边且lowbit比它大的第一个结点，所以只需要让i+=lowbit(i)。代码如下：

void add(int i,int x)
{
    //若需要其他操作，可以加一句：
    //A[i]+=x;
    while(i<=n)
    {
        S[i]+=x;i+=lowbit(i);
    }
}

查询前缀和的方法与之类似，只是i+=lowbit(i);改成了i-=lowbit(i);这里不再介绍证明方法，与上面类似。代码如下：

int query2(int i)
{
    int sum=0;
    while(i!=0)
    {
        sum+=S[i];i-=lowbit(i);
    }
    return sum;
}
int query(int l,int r)
{
    return query2(r)-query2(l-1);
}

最后，若有建议请提出。

本文永久更新链接地址：