本文共 4239 字，大约阅读时间需要 14 分钟。

树状(Binary Indexed Tree(BIT), Fenwick Tree)是一个查询和修改复杂度都为log(n)的数据结构。主要用于查询任意两位之间的所有元素之和，但是每次只能修改一个元素的值；经过简单修改可以在log(n)的复杂度下进行范围修改，但是这时只能查询其中一个的值(如果加入多个辅助数组则可以实现区间修改与区间查询)。——百度百科

树状数组作用就是给定一个数组，在log(n)时间内求数组内某个区间的和，并且可以在log(n)时间内修改其中的某个元素。本文只研究修改单个值，区间求和的情况。

需要维护一个C数组，如下图所示：

令这棵树的结点编号为C1，C2...Cn。令每个结点的值为这棵树的值的总和，那么容易发现：

C1 = A1

C2 = A1 + A2

C3 = A3

C4 = A1 + A2 + A3 + A4

C5 = A5

C6 = A5 + A6

C7 = A7

C8 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8

...

C16 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8 + A9 + A10 + A11 + A12 + A13 + A14 + A15 + A16

这里有一个有趣的性质：

设节点编号为x，那么这个节点管辖的区间为2^k（其中k为x二进制末尾0的个数）个元素。因为这个区间最后一个元素必然为Ax，

所以很明显：Cn = A(n – 2^k + 1) + ... + An

例如：C[6]这个结点，6的二进制为110，末尾有1个0，所以它的管辖区间是2^1 = 2个元素，即5和6。

求2^k的简便方法是使用位运算：

int lowerbit(int x)

利用机器补码特性，也可以写成：

int lowerbit(int x)

解释：lowbit(k)就是把k的二进制的高位1全部清空，只留下最低位的1,比如10的二进制是1010,则lowbit(k)=lowbit(1010)=0010(2进制)，介于这个lowbit在下面会经常用到，这里给一个非常方便的实现方式，比较普遍的方法lowbit(k)=k&-k，这是位运算，我们知道一个数加一个负号是把这个数的二进制取反+1，如-10的二进制就是-1010=0101+1=0110，然后用1010&0110，答案就是0010了，也就是2^k的结果。

修改某个值时：

如果要修改一个值，那么需要修改所有管辖这个数的C[]数组的值。

比如要修改a[3]，由于a[3]同时被c[3]、c[4]、c[8]（假设只有8个数字）管辖，那么更新a[3]的时候，就需要同时修改c[3]、c[4]、c[8]。

修改代码：

void add(int k,int num)  //将第k个元素加上num{         while(k<=n)          {              tree[k]+=num;              k+=k&-k;          }  }

求和：

如果求1~n这个区间和的话，只需要将log（n）个C[]数组中的值想加即可。比如要求1~6这个区间的和，那就只需将C[6]和cC[4]相加即可。

求和代码：

int read(int k)//1~k的区间和  {         int sum=0;          while(k)          {              sum+=tree[k];              k-=k&-k;          }          return sum;  }

参考：

整体代码：

#include 
   
    #include 
    
     #define N 1005int c[N], n;int lowbit(int x){	return x&(-x);}void add(int k, int x){	while(k <= n){		c[k] += x;		k += lowbit(k);	}}int sum(int k)//求前k项和{    int s=0;    while(k>0)    {        s+=c[k];        k-=lowbit(k);    }    return s;}int main(){	int q, x, a, b;	while(~scanf("%d%d", &n, &q)){		memset(c, 0, sizeof(c));		for(int i = 1; i <= n; i ++){			scanf("%d", &x);			add(i,x);		}		while(q--){			scanf("%d%d", &a, &b);			int ans = sum(b) - sum(a-1);			printf("%d\n", ans);		}	}	return 0;}
    
   

上面讲的都是一维树状数组，树状数组也可以扩展到二维，即求和时改为求某个子矩阵的和。

举个例子来看看C[][]的组成。 

C[]数组在二维树状数组中需要同时管辖行和列，管辖的范围与一维相似，不论是行还是列都是管辖lowbit(i)的范围。

修改代码：

void modify(int x,int y,int data){    for(int i=x;i

求和代码：

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

整体代码：

#include
   
    #include 
    
     #include 
     
      #include
      
       using namespace std;const int MAXN = 1010;int c[MAXN][MAXN];int lowbit(int x){    return x & (-x);}void modify(int x,int y,int data){    for(int i=x;i
       
        0;i-=lowbit(i))        for(int j=y;j>0;j-=lowbit(j))            res+=c[i][j];    return res;}int main(){    int n,x,y,x1,y1, date;    char str[5];    scanf("%d",&n);    memset(c,0,sizeof(c));    while(n--)    {        scanf("%s",str);        if(strcmp(str,"add")==0)        {            scanf("%d%d%d",&x,&y, &date);            modify(x,y,date);        }        else {            scanf("%d %d %d %d",&x,&x1,&y,&y1);            int ans=get_sum(x1,y1)-get_sum(x-1,y1)-get_sum(x1,y-1)+get_sum(x-1,y-1);            printf("%d\n",ans);        }    }    return 0;}
       
      
     
    
   

转载地址：https://blog.csdn.net/zhj_fly/article/details/76643638 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！