树状数组

树状数组的作用

        实际上，树状数组算是线段树的小弟角色，树状数组能解决的问题线段树一定能解决，而线段树能解决的问题树状数组却不一定能解决。两者都是在区间进行操作，但是树状数组是不如线段树厉害的。但是树状数组的有点就在于常数小，并且短小精悍，手搓的时候就几行代码。

位运算

        树状数组涉及到大量位运算，这里不再多说，不会的同学先看看位运算、二进制的东西再学习树状数组。位运算其实并不难。

lowbit函数之前博客写了。

树状数组的原理

        为什么要利用lowbit函数？对树状数组有什么作用么？我们可以得到这样的图：

如果把lowbit函数的值作为这个位置储存的区域和，这样就可以完美覆盖所有位置。也就是，每一个数字管理一段区间。就像线段树一样。这就是为什么我们要利用lowbit函数。

        我们在维护、使用树状数组的时候，利用累加。原来数组上利用累加的时候是i++，这样遍历一次数组时间复杂度为O(n)，我们既然可以利用lowbit，那么累加的时候将i++改为i += lowbit(i)，这样虽然我们还是在原数组上跳跃，但是可以抽象成在一个树上按顺序遍历。

树状数组的区间维护

        我们利用数组查找时候O(1)的特点，直接修改对应的数值，即：tree[index] = n。这样是最开始的一步，接下来就是维护了。我们从index开始，根据lowbit进行遍历，即：i += lowbit(i)，每次循环就将tree[i] += n，这样就保证的了树状数组的更新。

树状数组的区间维护

        我们利用数组查找时候O(1)的特点，直接修改对应的数值。这样是最开始的一步，接下来就是维护了。我们从index开始，根据lowbit进行遍历，即：i += lowbit(i)，每次循环就将tree[i] += y，这样就保证的了树状数组的更新。

void add (int x,int y)
{
    for( ; x<=N; x+=x&-x)
        tree[x]+=y;
}

        跟线段树一样，操作是非常多变的，具体的操作有具体的写法，这里就随便写一个操作了。

树状数组的区间查询

        这里的区间查询很明显能感到是比线段树简单很多的，或者说查找的是前缀和。例如我们查找20，得到的是1-20的和，只能得到前缀无法得到具体的区间值。不过问题不大，我们可以通过求两次取差的方法获取区间值，例如：find(right) - find(left)。不过如果是大量的区间运算，麻烦一点写成线段树更好。

        跟更新相反，我们从x开始，利用lowbit进行递减，就可以一直减到1，就可以求出前缀和了。

int ask (int x)
{
    int ans = 0;
    for(; x; x -= x & -x)
        ans+=tree[x];
    return ans;
}

树状数组例题

HDU 1166

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<stdlib.h>
#include<queue>
#include<map>
#include<iomanip>
#include<math.h>
using namespace std;
typedef long long ll;
typedef double ld;

int i, j, k;
int x,y;
int T;
int n;
int a[50010],ans[50010];
char op[10];
void add (int x,int y)
{
    for( ; x<=n; x+=x&-x)
        ans[x]+=y;
}

void sub (int x,int y)
{
    for( ; x<=n; x+=x&-x)
        ans[x]-=y;
}

int ask (int x)
{
    int temp = 0;
    for(; x; x -= x & -x)
        temp += ans[x];
    return temp;
}

int main()
{
    scanf("%d",&T);
    int cas=1;
    while(T--)
    {
        printf("Case %d:\n",cas++);
        scanf("%d",&n);
        memset(ans, 0, sizeof ans);
        for(i=1; i <= n ; i ++)
        {
            scanf("%d ", &a[i]);
            add(i , a[i]);
        }
        while(~scanf("%s",&op))
        {
            if(op[0]=='E')
                break;
            else if(op[0]=='A')
            {
                scanf("%d %d",&x,&y);
                add(x,y);
            }
            else if(op[0]=='S')
            {
                scanf("%d %d",&x,&y);
                sub(x,y);
            }
            else
            {
                scanf("%d %d",&x,&y);
                int l=ask(x-1);
                int r=ask(y);
                printf("%d\n",r-l);
            }
        }

    }
    return 0;
}