树状数组必要的图解

这个图表示了对数组的变化，使得 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[i]的值代表了对应的i可以控制的区间，那么如果改变一个值后，只需要改变c数组中控制这个区间的c[i]就可以了

1.树状数组，两个最基本的操作，修改和查询

首先的条件是神一样的函数

int c[100010] ;

int lowbit(int x)
{
    return x&-x;
}这个函数可以使 i-=lowbit(i) 跳到i控制的区间的之前的节点  i += lowbit(i) 跳到i控制区间的之后的节点 ，也就是说可以由i跳到下一个控制区间包括i的位置

修改

void add(int i,int n,int d)
{
    while(i <= n)
    {
        c[i] += d;
        i += lowbit(i) ;
    }
}

查询

int sum(int i)
{
    int a = 0 ;
    while(  i )
    {
        a += c[i]  ;
        i -= lowbit(i) ;
    }
    return a;
}

在这个修改中由前向后修改，改变了所有c数组中控制区间包含i的值，查询时有后向前搜索，log(n)的时间搜索到整个的值

2. 在树状数组中不仅可以修改一个值，也可以修改区间内的所有值

1.如果每次查询的是数组中某一个值，那么用树状数组比线段树更省时间，例，如果要修改[x,y]内的值，可以用数组a保留初始的情况，数组b表示修改的情况(b[i]表示，由i到n的所有数+b[i])，那么对于[x,y]就可以表示成 b[x] += 1 , b[y+1] += -1 ；这样由b数组写出的树状数组中，对于计算i时，由b[1] + b[2] + b[3] 。。b[i] 表示了对i所有的修改

2.如果查询的是一段区间和，也可用树状数组写出，同上一样数组a保留初始情况，数组b表示修改的情况(b[i]表示由i到n的所有修改)，那么求区间[x,y]的和时 sum = Sy - Sx；以Sx为例  Sx = 初始值+修改的值，修改的值 = b[1] * x + b[2] * (x-1) + 。。b[x]*1 = ( x+1 )*(b[1]+b[2]。。+b[x]) - ( b[1]*1 + b[2]*2 + 。。b[x]*x ) 用两个树状数组表示b[i]的和，b[i]*i的和

3 二维的树状数组

二维的树状数组的修改和查询操作

修改

void add(int i,int j,int n,int d)
{
    int x , y ;
    for(x = i ; x <= n ; x += lowbit(x))
        for(y = j ; y <= n ; y += lowbit(y))
            c[x][y] += d ;
}

查询

int sum(int i,int j)
{
    int a = 0 , x , y ;
    for( x = i ; x > 0 ; x -= lowbit(x) )
        for( y = j ; y > 0 ; y -=lowbit(y) )
            a += c[x][y] ;
    return a;
}

原理同一维相同，不过在二维中c[i][j] 表示由[1,1]到[i,j]的矩形的和

同样在修改一个值时，可以方便的查询出一段区间的和；修改一段区间时，方便的查询一个数的值

3, 三维树状数组

修改

int add(int i,int j,int k,int n,int d)
{
    int x , y , z ;
    for(x = i ; x <= n ; x += lowbit(x))
        for(y = j ; y <= n ; y += lowbit(y))
            for(z = k ; z <= n ; z += lowbit(z))
                c[x][y][z] += d ;
}

查询

int sum(int i,int j,int k)
{
    int a = 0 , x , y , z ;
    for(x = i ; x > 0 ; x -= lowbit(x))
        for(y = j ; y > 0 ; y -= lowbit(y))
            for(z = k ; z > 0 ; z -= lowbit(z))
                a += c[x][y][z];
    return a ;
}

用法同上

4.例题

1.poj2481，对s和e排序，保证对于第i头牛时，所有比i强壮的牛都统计过，并且对于标记的数组来说在i的前面，方便用树状数组统计前面的数量

2.poj2352，星的问题，同上一样，使得每个等级比它小的都会在它之前统计过

3.poj2299，对问题的转化，问需要多少次交换，可以转化为从第一个开始每次都是它之前的变为有序的，那么对于第i个只需要交换在i之前的，且比i大的，题目就转化为求逆序数的问题，使用树状数组求逆序数，可以向前统计比它小的个数，用（i-sum）求出i之前比它大的数目，或者直接向后统计，比他大的数目

4.hdu1556，每次修改了一段范围的值，问某一个数的值

5.poj2182，杂乱的牛站到一起，给出的数表示在该牛之前有多少序号比该牛小的，由后向前统计，那么第i个牛的序号 = 在还没用的序号，找出第a[i]+1个，使用树状数组计算序号为k是当前的第几个，使用二分找到第a[i]+1个，那个序号就是牛a[i]的序号。（注意为了防止一个序号被用多次，找到的序号尽可能的向左）

6.poj3468，树状数组解法

7.poj2155，二维树状数组，修改一个矩形的数，问某个数的大小

8.hdu3584，三维树状数组，同上。