树状数组 简单介绍

树状数组

即用数组模拟树形结构，令修改和查询的时间复杂度变为O(logN)，能用树状数组解决的问题都可以用线段树解决，树状数组相对于线段树功能更为局限（一般是对 区间和 进行维护），但树状数组花费空间更小（数组大小和原数组相同），更易编写。

注意点：

具体操作

先引入一个函数：lowbit(x) —— 取x二进制最低位的1的值
例如 lowbit( (101011000)₂ ) = 2³

int lowbit(int x)
{
	return x&(-x);
}

①单点更新（令 a[i]+k ）

包含 a[i] 的树状数组有：c[i]、c[ i+lowbit[i] ]、c[ pre+lowbit[pre] ] …

void updata(int i,int k)   //令a[i]+k
{
	while(i<=n)
	{
		c[i]+=k;
		i+=lowbit(i);
	}	
}

②区间查询（求 a[1]到a[i] 的和，即位置 i 的前缀和）

位置 i 的前缀和 sum[i] = c[i] + c[ i-lowbit[i] ] + c[ pre-lowbit[pre] ] …

int query(int i)   //求 a[1]到a[i] 的和
{
	int ret = 0;
	while(i>0)
	{
		ret+=c[i];
		i-=lowbit(i);
	}
	return ret;
}

③区间更新

这个就需要用到差分数组，然后对差分数组进行相应的维护，要注意，区间查询的操作也要进行改动。

模板题：

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=5e4+50;
int N,a[maxn],c[maxn];
int lowbit(int x)
{
    return x&(-x);
}
void updata(int i,int k)
{
    while(i<=N)
    {
        c[i]+=k;
        i+=lowbit(i);
    }
}
int query(int i)
{
    int ret=0;
    while(i>0)
    {
        ret+=c[i];
        i-=lowbit(i);
    }
    return ret;
}
int main()
{
    int T,kase=0;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&N);
        memset(c,0,sizeof(c));   //初始化为0
        for(int i=1;i<=N;i++)
        {
            scanf("%d",&a[i]);
            updata(i,a[i]);
        }
        printf("Case %d:\n",++kase);
        char op[10];
        int i,j;
        while(scanf("%s",op)&&op[0]!='E')
        {
            scanf("%d %d",&i,&j);
            if(op[0]=='A')       //第i个+j
                updata(i,j);
            else if(op[0]=='S')  //第i个-j，即+(-j)
                updata(i,-j);
            else                //询问i~j的和
                printf("%d\n",query(j)-query(i-1));
                                //query返回的是前缀和，所以要sum[j]-s[i-1]
        }
    }
    return 0;
}