简单理解树状数组（单个数据）

雨点打透心脏的1/2处 2022-06-13 02:37 210阅读 0赞

我们把原数组设为 **a\[\]** ，然后数组是从 **1** 开始的，一共 **n** 个数，存入原始数组

for(int i = 1; i <= n; i++) { scanf("%d", &x); updata(i, x); }

每次输入的时候都要 **updata**，那么 **updata** 是什么呢，不要急，代码如下：

void updata(int x, int v) {
        while(x <= n) {
            a[x] += v;
            printf("a[%d] = %d\n", x, a[x]);
            x += lowbit(x);
        }
    }

从代码中可以看出 **x** 为此时 **a** 数组的下标， **v** 为 **a\[x\]** 的值，即下标为 **x** 时的 **a** 数组对应的值，赋值之后我们看到了一个 **lowbit（）** 的函数，**lowbit**的代码很简单，原理是二进制，解释如下：  
假设现在传入函数**updata**  
**x = 2** ， **n = 9** ，结果如下：

**9**  
**2**  
**a\[1\] = 2**  
**a\[2\] = 2**  
**a\[4\] = 2**  
**a\[8\] = 2**  
(忘记怎么插图了..)

数组 **a** 的下标值从 **1** 到了 **8** ，这就是**lowbit**做的工作，再看一下下面的样例：  
**100**  
**3**  
**a\[1\] = 3**  
**a\[2\] = 3**  
**a\[4\] = 3**  
**a\[8\] = 3**  
**a\[16\] = 3**  
**a\[32\] = 3**  
**a\[64\] = 3**  
**1**  
**a\[2\] = 4**  
**a\[4\] = 4**  
**a\[6\] = 4**  
**a\[8\] = 4**  
**a\[16\] = 4**  
**a\[32\] = 4**  
**a\[64\] = 4**  
**4**  
**a\[3\] = 4**  
**a\[4\] = 8**  
**a\[6\] = 8**  
**a\[8\] =8**   
**a\[16\] = 8**  
**a\[32\] = 8**  
**a\[64\] = 8**

每次传入的下标值是 **i** ，是从 **1** 开始循环到 **n** 的（在主函数中定义）， 在第一组中下标是从 **1** 开始的，第二组是从 **2** 开始的，以此类推。  
除去第一项，右边则是相加，还有个规律是 后一项是前一项的 **两** 倍，这就是**lowbit**做到的，**n** 来限制下标的大小，下标一定不能大于 **n** 。  
说了这么多，其实就是用一个方法来记录数据。  
那么记录之后怎么用呢，用一个函数来读取，读取的方式也是用 **lowbit** 的方式

int sumdata(int x) {
        int sum = 0;
        while(x > 0) {
            sum += a[x];
            x -= lowbit(x);
        }
        return sum;
    }

**x** 为 **a** 的下标，表示从 第 **1** 个开始到第 **x** 个的总和，但是如果询问从第 **i** 个到第 **j** 个总和为多少要写成  
**sumdata(j) - sumdata(i-1)**  
例题：  
[http://acm.hdu.edu.cn/showproblem.php?pid=1166][http_acm.hdu.edu.cn_showproblem.php_pid_1166]  
AC代码：

#include<iostream>
    #include<cstdio>
    #include<cmath> 
    #include<cstring>
    #include<algorithm>
    #include<stdlib.h>
    #define MAXN 50500
    #define maxint 9999999
    using namespace std;
    
    int n, a[MAXN];
    
    int lowbit(int x) {
        return x&(-x);
    }
    
    void updata(int x, int v) {
        while(x <= n) {
            a[x] += v;
    // printf("a[%d] = %d\n", x, a[x]);
            x += lowbit(x);
        }
    }
    int sumdata(int x) {
        int sum = 0;
        while(x > 0) {
            sum += a[x];
            x -= lowbit(x);
        }
        return sum;
    } 
    int main() {
        //freopen("C:\\Users\\Administrator\\Desktop\\out.txt","w",stdout);
        int t, kase = 0;
        scanf("%d", &t);
        while( t-- ) {
            memset(a, 0, sizeof(a));
            printf("Case %d:\n",++kase);
            int x, v;
            scanf("%d", &n);
            for(int i = 1; i <= n; i++) {
                scanf("%d", &x);
                updata(i, x);
            }
            char str[20];
            for(;;) {
                scanf("%s", str);
                if(str[0] == 'E') break;
                scanf("%d %d", &x, &v);
                if(str[0] == 'A') updata(x, v);
                else if(str[0] == 'S') updata(x, -v);
                else if(str[0] == 'Q') printf("%d\n", sumdata(v) - sumdata(x-1));
            }
        }
        return 0;
    }

[http_acm.hdu.edu.cn_showproblem.php_pid_1166]: http://acm.hdu.edu.cn/showproblem.php?pid=1166