树状数组入门(简单的原理讲解)

亦凉 2021-11-09 15:48 313阅读 0赞

树状数组可以解决什么样的问题：

这里通过一个简单的题目展开介绍，先输入一个长度为n的数组，然后我们有如下两种操作：

1.  输入一个数m，输出数组中下标1~m的前缀和
2.  对某个指定下标的数进行值的修改

多次执行上述两种操作

--------------------

**寻常方法**  
对于一个的数组，如果需要求1~m的前缀和我们可以将其从下标1开始对m个数进行求和，对于n次操作，时间复杂度是O(n^2)，对于值的修改，我们可以直接通过下标找到要修改的数，n次操作时间复杂度为O(n)，在数组n开得比较大的时候，求前缀和的效率显得低了

*  那么有人提出了一种优化的方式：  
    初始我们用一个数组A的保存每个位置的初始值，然后用一个辅助数组B存放的是下标为i的时候A数组的前i个的和（前缀和），那么当我们需要查询m个数的前缀和的时候只要直接使用下标对B数组进行查询即可，n次查询，时间复杂度为O(n)，而此时，对于单点更新值的维护消耗，由原来的O(n)变成了O(n^2)，因为每一次与更新单点值都会对后面的已经计算好的B数组前缀和的值造成影响，需要不断更新B数组的值，n次更新维护的消耗自然就变成了O(n^2)，更新的效率变得低下

**树状数组**  
那么是否有一种方法可以让查询和更新的时间复杂度都小一些呢，至少可以令人接受，这里将介绍树状数组如何处理前缀和查询和单点更新的问题，对于n次操作，时间复杂度都为O(nlogn)

*  借用百度百科上的图片  
    ![图1.jpg][1.jpg]  
    ![图2.jpg][2.jpg]

如图，对于一个长度为n的数组，A数组存放的是数组的初始值，引入一个辅助数组C（我们通过C数组建立树状数组）

C1 = A1  
C2 = C1 + A2 = A1 + A2  
C3 = A3  
C4 = C2 + C3 + A4 = A1 + A2 + A3 + A4  
C5 = A5  
C6 = C5 + A6 = A5 + A6  
C7 = A7  
C8 = C4 + C6 + C7 + A8 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8

**我们称C\[i\]的值为下标为i的数所管辖的数的和，C\[8\]存放的就是被编号8所管辖的那些数的和（有8个），而下标为i的数所管辖的元素的个数则为2^k个（k为i的二进制的末尾0的个数）举两个例子查询下标m==8和m==5所管辖的数的和**

*  8 = 1000，末尾3个0，故k == 3，所管辖的个数为2^3 == 8，C8是8个数的和
 *  5 = 0101，末尾没有0，故k == 0，所管辖的个数为2^0 == 1，C5是一个数的和（它本身A5）

而对于输入的数m，我们要求编号为m的数的前缀和A1~Am（**这里假设树状数组已经建立，即C1~C8的值已经求出，别着急，在本文的最下方会做出建立树状数组的过程讲解，因为现在是在求前缀和，就假设C数组已经可用了吧**）举两个例子m==7和m==6（sum(i)表示求编号为i的前缀和）

*  m==7 sum(7) = C7 + C6 + C4  
    那么我们是怎么得到编号7是由哪几个C\[i\]求和得到呢（C4, C6, C7怎么得到的），这里有介绍一种巧妙的方法：  
    **对于查询的m，将它转换成二进制后，不断对末尾的1的位置进行-1的操作，直到全部为0停止**  
    7的二进制为0111（C7得到），那么先对0111的末尾1的位置-1，得到0110 == 6（C6得到），再对0110末尾1位置-1，得到0100 == 4（C4得到），最后对0100末尾1位置-1后得到0000（结束信号），计算停止，至此C7，C6，C4全部得到，求和后就是m == 7时它的前缀和
 *  m==6 sum(6) = C6 + C4  
    m == 6时也是一样，先转成2进制等于0110，经过两次变换后为0100（C4）和0000（结束信号），那么求和后同样也得到了预计的结果

**这里要介绍一个高效的方法，lowbit(int m)，这是一个函数，它的作用是求出m的二进制表示的末尾1的位置，对于要查询m的前缀和，m = m - lowbit(m)代表不断对二进制末尾1进行-1操作，不断执行直到m == 0结束，就能得到前缀和由哪几个Cm构成，十分巧妙，lowbit也是树状数组的核心**

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

关于m&(-m)很多童鞋可能感到困惑，那么就不得不提及一下负数在计算机内存中的存储形式，负数在计算机中是以补码的形式存储的，如13的二进制表示为1101，那么-13的二进制而将13二进制按位取反，然后末尾+1，即0010 + 0001 = 0011，那么1101 & 0011== 0001，很显然得到m == 13二进制末尾1的位置是2的0次方位，将13 - 0001 == 12，再对12执行lowbit操作，1100 & 0100 == 0100，也很轻易得到了m == 12时二进制末尾1的位置是2的2次方位，将12 - 0100 == 8，再对8执行lowbit操作，0100 & 1100 == 0100，得到m == 8时二进制位是2的2次方位，8 - 0100 == 0（结束操作），通过循环得到的13，12，8，则sum(13) == C13 + C12 + C8

**求前缀和的代码**

int ans = 0;
    int getSum(int m){
        while(m > 0){
            ans += C[m];
            m -= lowbit(m);
        }
    }

对于n次前缀和的查询，时间复杂度为O(nlogn)  
**接下来讲解单点更新值**  
对于输入编号为x的值，要求为它的值附加一个value值，我们把图再一次拿下来  
![图3.jpg][3.jpg]

假设x==2，value==5，那么我们先找到A\[2\]的位置，通过观察我们得知，如果修改了A\[2\]的值，那么管辖A\[2\]的C\[2\]，C\[4\]，C\[8\]的前缀和都要加上value（所有的祖先节点），那么和查询类似，我们如何得到C2的所有祖先节点呢（因为C2和A2的下标相同所以更新时查询从C\[x\]开始），依旧是上述的巧妙的方法，但是我们把它倒过来  
**对于要更新x位置的值，我们把x转换成二进制，不断对二进制最后一个1的位置+1，直到达到数组下标的最大值n结束**

*  对于给出的例子x==2，假设数组下标上限n==8，x转换成二进制后等于0010（C2），对末尾1的位置进行+1，得到0100（C4），对末尾的1的位置进行+1，得到1000（C8），循环结束，对C2，C4，C8的前缀和都要加上value，当然不能忘记对A\[2\]的值+value，单点更新值过程结束

**给出代码**

void update(int x, int value){
        A[x] += value;    //不能忘了对A数组进行维护，尽善尽美嘛
        while(x <= n){
            C[x] += value;
            x += lowbit(x);
        }
    }

对于n次更新操作，时间复杂度同样为O(nlogn)

这里有一个注意事项，我们对于求前缀和与单点更新时，树状数组C是拿来直接使用的，那么问题来了，树什么时候建立好的，我怎么不知道？?

**事实上，对于一个输入的数组A，我们一次读取的过程，就可以想成是一个不断更新值的过程（把A1~An从0更新成我们输入的A\[i\]），所以一边读入A\[i\]，一边将C\[i\]涉及到的祖先节点值更新，完成输入后树状数组C也就建立成功了**

*  完整代码如下：

#include<stdio.h>
    #include<string.h>
    
    int a[10005];
    int c[10005];
    int n;
    
    int lowbit(int x){
        return x&(-x);
    }
    
    int getSum(int x){
        int ans = 0;
        while(x > 0){
            ans += c[x];
            x -= lowbit(x);
        }
        return ans;
    }
    
    void update(int x, int value){
        a[x] += value;
        while(x <= n){
            c[x] += value;
            x += lowbit(x);
        }
    }
    
    int main(){
        while(scanf("%d", &n)!=EOF){    //用于测试n == 8 
            memset(a, 0, sizeof(a));
            memset(c, 0, sizeof(c));
            for(int i = 1; i <= n; i++){
                scanf("%d", &a[i]);     //a[i]的值根据具体题目自己安排测试可以1，2，3，4，5，6，7，8 
                update(i, a[i]);        //输入的过程就是更新的过程 
            }
            int ans = getSum(n-1);      //用于测试输出n-1的前缀和 输出28 
            printf("%d\n", ans);
        }   
        return 0;
    }

[1.jpg]: /images/20211109/d04acc5f933f43ab980eb149c711d260.png
[2.jpg]: /images/20211109/5b4f2728302b476fb21ef7f6a3129919.png
[3.jpg]: /images/20211109/b1daebe7eb4d4978a0662700f752c9c9.png