树状数组

忘是亡心i 2022-07-26 08:44 243阅读 0赞

# 树状数组 #

## 树状数组：用线性数据结构的方法解决动态统计子树权和的问题。 ##

类似于线段树，将区间分成小段，方便计算权和。

举个栗子，将a数组构造成树状数组c。

如果a数组中共有8个元素a\[1\]~a\[8\]，注意这里数组的下标要从1开始，那么:

c\[1\]=a\[1\]

c\[2\]=a\[1\]+a\[2\]

c\[3\]=a\[3\]

c\[4\]=a\[1\]+a\[2\]+a\[3\]+a\[4\]

c\[5\]=a\[5\]

c\[6\]=a\[5\]+a\[6\]

c\[7\]=a\[7\]

c\[8\]=a\[1\]+a\[2\]+a\[3\]+a\[4\]+a\[5\]+a\[6\]+a\[7\]+a\[8\]

下面说一下为什么c数组是这样的，还有对c数组的一些操作。

## 一、c数组的来历 ##

线段树是直接递归二分来划分，而树状数组需要通过lowbit(i)这个函数来确定划分范围。

int lowbit(int x)//计算二进制数x右方的第一位1对应的权
    {
        return x&(-x);
    }

①c\[k\]存储从a\[k\]开始向前数lowbit(k)个元素之和，即c\[k\]=a\[k\]+a\[k-1\]+a\[k-2\]+...+a\[i-(2^k)+1\]。

②lowbit(k)=k&(-k)，在二进制中，-k是取反加1，这个函数是求整数k的二进制表示中右边第一个1在二进制中代表的权值。

例如：

#include<iomanip>
    #include<iostream>
    #include<stdlib.h>
    #include<cstdio>
    #include<cmath>
    using namespace std;
    
    int main()
    {
        char str[25];
        int i;
        for(i=1; i<=10; ++i)
        {
            itoa(i,str,2);
            cout<<"i="<<i<<"  "<<(i&-i)<<" 二进制 "<<str<<endl;
        }
        return 0;
    }

运行结果：

![Center][]

由图，可以得到i对应的lowbit(i)值。

所以:

当i=1时，lowbit(1)=1，c\[1\]=a\[1\]；

当i=2时，lowbit(2)=2，c\[2\]=a\[2\]+a\[1\]，c\[2\]由a\[2\]及其之前共计lowbit(2)=2个数相加得到；

当i=3时，lowbit(3)=1，c\[3\]=a\[3\]；

当i=4时，lowbit(4)=4，c\[4\]=a\[4\]+a\[3\]+a\[2\]+a\[1\],c\[4\]由a\[4\]及其之前共计lowbit(4)=4个数相加得到；

………………………………

下面依次类推，所以就得到上面c数组的各个值。

## 二、调整整棵子树 ##

从c\[i\]依次调整这棵子树，数组下标是i+=lowbit(i)

举个栗子：当改变a\[4\]的值的时候，c\[4\]与a\[4\]、a\[3\]、a\[2\]、a\[1\]都有关，这四个都要改变权值，

那么计算出4、3、2、1这四个数组下标的公式就是i+=lowbit(i)。

例如如下代码：

void change(int x)//x是a数组的下标
    {
        int i;
        if(条件满足)
            for(i=x; i<cnt; i+=lowbit(i))//调整a[x]这一棵子树
                c[i]改变;
    }

## 三、计算子树权值之和 ##

与上面的情况类似，依次找出这个节点相关的所有节点，即相应的数组下标，再累加起来就是权值之和。

例如如下代码：

int sum(int x)//计算节点x子树权值之和
    {
        int i,res=0;//res是权值和
        for(i=x; i>0; i-=lowbit(i))
            res+=c[i];
        return res;
    }

## 四、二维树状数组 ##

和一维的树状数组一样，就是更新和查询稍微作出一点改变。可以看一下模板入门题（传送门→）：[POJ 1195][]

更新和查询的代码改变如下：

void update(int x,int y,int num)
    {
        int i,j;
        for(i=x; i<=n; i+=lowbit(i))
            for(j=y; j<=n; j+=lowbit(j))
                c[i][j]+=num;
    }
    int sum(int x,int y)
    {
        int i,j,res=0;
        for(i=x; i>0; i-=lowbit(i))
            for(j=y; j>0; j-=lowbit(j))
                res+=c[i][j];
        return res;
    }

以上就是我自己学习了一上午之后对树状数组的简单的认识，下面贴一道入门题[POJ 3321-Apple Tree][]（←这里是传送门），希望这道题对理解树状数组有很好的帮助。

[Center]: /images/20220724/bfd674eb690540e297df0efe0dc0f8a9.png
[POJ 1195]: http://blog.csdn.net/mikasa3/article/details/51332195
[POJ 3321-Apple Tree]: http://blog.csdn.net/mikasa3/article/details/51104809