树状数组

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

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

举个栗子，将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;
}