树状数组详解

电玩女神 2023-07-13 04:28 1阅读 0赞

### 树状数组是干什么的？ ###

一句话概括：树状数组是查询动态数组前缀和的。一般而言，对于一个值经常变化的数组，我们修改某一个值的复杂度是O(1)，查询某一个前缀和是O(n)，而使用树状数组，则可以做到查询和修改的复杂度均为O(logn)，降了一个数量级。

### 树状数组的结构和原理 ###

引用百度百科的图片：  
![在这里插入图片描述][format_png]  
上图为一个树状数组的结构：  
下面我用 A \[ n \] A\[n\] A\[n\]表示原数组的元素， T \[ n \] T\[n\] T\[n\]表示树状数组的元素。可见每一个树状数组的元素代表的一段原数组的元素的和，例如  
 T \[ 12 \] = A \[ 12 \] + A \[ 11 \] + A \[ 10 \] + A \[ 9 \] T\[12\] = A\[12\] + A\[11\] + A\[10\] + A\[9\] T\[12\]=A\[12\]\+A\[11\]\+A\[10\]\+A\[9\]  
 T \[ 11 \] = A \[ 11 \] T\[11\] = A\[11\] T\[11\]=A\[11\]  
 T \[ 10 \] = A \[ 10 \] + A \[ 9 \] T\[10\] = A\[10\] + A\[9\] T\[10\]=A\[10\]\+A\[9\]  
 T \[ 9 \] = A \[ 9 \] T\[9\] = A\[9\] T\[9\]=A\[9\]  
 T \[ 8 \] = A \[ 8 \] + A \[ 7 \] + A \[ 6 \] + A \[ 5 \] + A \[ 4 \] + A \[ 3 \] + A \[ 2 \] + A \[ 1 \] T\[8\] = A\[8\] + A\[7\] + A\[6\] + A\[5\] + A\[4\] + A\[3\] + A\[2\] + A\[1\] T\[8\]=A\[8\]\+A\[7\]\+A\[6\]\+A\[5\]\+A\[4\]\+A\[3\]\+A\[2\]\+A\[1\]  
 T \[ 7 \] = A \[ 7 \] T\[7\] = A\[7\] T\[7\]=A\[7\]  
 T \[ 6 \] = A \[ 6 \] + A \[ 5 \] T\[6\] = A\[6\] + A\[5\] T\[6\]=A\[6\]\+A\[5\]  
 T \[ 5 \] = A \[ 5 \] T\[5\] = A\[5\] T\[5\]=A\[5\]  
 T \[ 4 \] = A \[ 4 \] + A \[ 3 \] + A \[ 2 \] + A \[ 1 \] T\[4\] = A\[4\] + A\[3\] + A\[2\] + A\[1\] T\[4\]=A\[4\]\+A\[3\]\+A\[2\]\+A\[1\]  
 T \[ 3 \] = A \[ 3 \] T\[3\] = A\[3\] T\[3\]=A\[3\]  
 T \[ 2 \] = A \[ 2 \] + A \[ 1 \] T\[2\] = A\[2\] + A\[1\] T\[2\]=A\[2\]\+A\[1\]  
 T \[ 1 \] = A \[ 1 \] T\[1\] = A\[1\] T\[1\]=A\[1\]  
可以发现每个树状数组的元素保存的是一段数据的和，如果我们想要得到12的前缀和，那么可以通过  
 T \[ 12 \] + T \[ 8 \] T\[12\] + T\[8\] T\[12\]\+T\[8\]得到，可以再 O ( l g N ) O(lgN) O(lgN)的得到，同样如果要更改 A \[ 6 \] A\[6\] A\[6\]的值，我们要把 T \[ 6 \] , T \[ 8 \] , T \[ 16 \] T\[6\],T\[8\],T\[16\] T\[6\],T\[8\],T\[16\]的要同时修改掉，更改的时间复杂度是 O ( l g N ) O(lgN) O(lgN)，这样我们就可以维护动态的前缀和了。  
这里有一个挺难发现的规律，对于树状数组的每一项，他到底是管辖多少个元素呢？比如 T \[ 12 \] T\[12\] T\[12\]管辖四个元素。其实 T \[ i \] T\[i\] T\[i\]管辖元素的个数是 2 k ， k 2^k，k 2k，k的值是 i 的二进制末尾连续0的个数，大家可以自行验证一下。

### Lowbit运算 ###

上回合说到，我们要想得到树状数组的元素，比如 T \[ i \] T\[i\] T\[i\]，必须要知道i的二进制末尾零的个数 k k k，然后 2 k 2^k 2k,为 T \[ i \] T\[i\] T\[i\]管辖的范围。前辈给我们提供了非常简洁的做法快速计算  i i i 对应的 2 k 2^k 2k，这个运算有专门的名字叫Lowbit运算。

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

函数的参数是 T \[ i \] T\[i\] T\[i\]中的  i i i ,返回值是 2 k 2^k 2k，为什么会这样，大家首先要了解计算机是怎么存储负数的，然后就明白了。

### 求前缀和 ###

有上面的介绍，我们就可以通过Lowbit运算轻易求出元素的前缀和。

int getSum(int i){
        
        int res = 0;
        while(i > 0){
        
            res += T[i];
            i -= lowbit(i);
        }
        return res;
    }

### 更新树状数组元素 ###

同样对于更新数组元素 A \[ i \] A\[i\] A\[i\]的过程，我们只需要将包含 A \[ i \] A\[i\] A\[i\]的所有 T \[ \] T\[\] T\[\]，都进行更改就可以了。

// 对指定A[i]加上value操作
    void update(int i, int value){
        
        A[i] += value;    //不能忘了对A数组进行维护，尽善尽美嘛
        while(i <= n){
        
            T[i] += value;
            i += lowbit(i);
        }
    }

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9ia2ltZy5jZG4uYmNlYm9zLmNvbS9waWMvOTYwYTMwNGUyNTFmOTVjYTVlNTg4NDU5Y2YxNzdmM2U2NjA5NTJhYg?x-oss-process=image/format,png