【引言】假如我们有一个长度为N的数组，我们需要频繁地进行如下两种操作：

（1）修改下标为 i 的某个元素的值；

（2）查询下标 L 到 R的区间的元素和。

如果我们采用朴素的算法，很显然，操作1的时间复杂度是O（1），频繁修改一点问题没有，但是操作2的时间复杂度为O（R - L），试想一下，如果频繁地查询效率是极低的。比如说N = 10⁸ 查询次数M = 10⁶，这样总的时间复杂度达到O（NM）10¹⁴，是根本不能忍受的。

 

【问题分析】首先我们分析一下采用朴素的算法它究竟慢在哪里。比如说我之前修改了a[7] 现在我要查询a[8] ~ a[10]，我每次查询区间和都要重新算一遍。那么我们可不可以把区间和事先存起来，存在另外一个数组 C[]中，这样我们在查询区间和的时候就直接O（1）地调用就好了。

存储任意L - R的区间和是不现实的，这个C数组要开成二维，空间占用10¹⁶。

 

【问题解决】有人提出来可以构造一个a数组的前缀和数组，这样查询L-R区间的和就相当于求C[R] - C[L-1] ！真是个好主意。

我们来考察这个想法合不合适，查询复杂度我们降到了O（1），那么修改的复杂度呢？

我们光修改原数组肯定是不行的，如果要维持查询区间和为O（1）的复杂度，那么每次对原数组单点修改的时候必须对C数组进行相应地修改。我们可以思考一下，如果我们修改了a[7]，那么我们要修改C数组的那些项，很显然，C[1] ~ C[6]是不用改的，因为他们不包含a[7]。但是对于C[7] C[8] C[9].......我们都要进行修改，改多少呢，增加一个差量，比如说我把a[7]从9改成5，那么C[7] C[8] C[9]......都要增加一个-4.

我们可以看出，尽管求区间和的复杂度降为O（1）但修改的复杂度提高至O（N）。这是不行的。

【进一步解决】

我们引入一种很优雅的数据结构：树状数组。

我们先不给出树状数组的构建规则，先看一下前面的特殊情况推理出一般性的规律。

 

 

观察C数组和A数组的关系，我们可以发现：

C[1] = A[1] 

C[2] = A[1] + A[2] 

C[3] = A[3]

C[4] = C[2] + C[3] + A[4] = A[1] + A[2] + A[3] + A[4] ;

C[5] = A[5]

C[6] =C[5] + A[6] = A[5] + A[6] 

C[7] = A[7] 

C[8] = C[4] + C[6] + C[7] +A[8] = A[1] + A[2] + A[3] + A[4] + A[5] + A[6] + A[7] +A[8]

C[9] = A[9]

 

【构建规则】我们从上述特例中找找C[i]和A数组有什么关系。我们把 i 写成二进制的形式。

比如C[4] , C[100] = A[100] + A[11] + A [10] + A[1] 

C[5],  C[101] = A[101]

C[6] , C[110] = A[110] + A[101]

C[7] , C[111] = A[111]

不难发现，求C[i] 时候, 如果把 i 的最低位的1所代表的的权值求出，记为K，那么C[i] 就是 A[i] + A[i - 1] + ......+ A[i - K + 1]。也就是从A[i]开始往左数K个元素直到A[i - K + 1]，把这些值加起来。 

比如 C[6], C[110] ,最低位1权值为K = 2，6 - 2 + 1 = 5,所以最多加到A[5]  ,所以C[6] = A[6] + A[5]

 

这就是树状数组C[i] 相对于原数组A[i] 的构建规则。求C[i] 时候, 如果把 i 的最低位的1所代表的的权值求出，记为K，那么C[i] 就是 A[i] + A[i - 1] + ......+ A[i - K + 1]

 

【查询与修改的方法】

一、查询区间和方法

设SUM（x）是区间1到X的元素和。

假如我们要求SUM（7）怎么求？是不是就是C[4] + C[6] + C[7]？

这是怎么实现的呢？我们将7写成2进制 ，SUM（111） = C[111] + C[110] + C[100]

再举一个例子， 求SUM(6)  SUM(110) = C[110] + C[100]

 SUM(9),  SUM(1001) = C[1001] + C[1000]

我们可以发现，设SUM(X) = C[P1] + C[P2] + ......+ C[Pk]   =   

那么P_i是P_i-1的值减去P_i-1最低位那一位的1所代表的的权值，直到P_i = 0为止。仔细验算一下是不是？

 所以在求SUM(X) 时， SUM(X) =  （其中Pi是不断变化的，Pi是上一次求出的Pi 减去其最低位1代表的权值）

 

二、单点修改方法

我们知道在修改原数组某一个位置的值时，树状数组必须要进行相应的变化。比如说把A[i]的值增加 X， 那么树状数组哪些元素需要增加呢？

那就要看哪些C[j] 控制了A[i]，根据上面所总结出的树状数组的构建规则，我们可以知道：C[i]要增加X， C[i + K]需要增加 X（K是i最低位的1所代表的权值）, 然后i 更新为 i+K, K的值也根据i更新

C[i+K]需要增加X，继续更新i = i + K,更新K......一直迭代下去直到i = N (肯定不能超出数组长度啊)

 

【子问题提出】：不论在构建C数组还是在查询区间和的过程中，都需要计算这样 一个东西：求数X的最低位的1所代表的的权值。

那么如何求一个二进制数最后一个1所代表的的权值呢？

原理：给定一个正数X， 先求出-X（正数补码还是本身，负数补码就是把负数原码第一个1和最后一个1之间的所有位全部取反，其余位不变。）

比如6,6的相反数是-6 ，-6原码是10110，它在计算机中是以补码形式表示的，补码是11001 + 1 = 11010  其实也就是原码的第一个1和最后一个1之间的位全部取反然后其他位不变。

再进行X & (-X)   （结合补码特点，这就是为什么可以取出最低位的1的原因）

也就是 （00110） & （11010） = 10 = 2，这就把最低位的1所代表的的权值计算出来了。

【代码实现】

原数组a[i]  树状数组 c[i] 下标从1开始

（1）取X最低位1所代表的权值的方法  lowbit(int x)

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

 （2）单点修改方法

 

void add(int x , ll val){    while(x <= n){        c[x] += val;        x += lowbit(x);    }}

 

（3）区间查询 1~X

int query(int x){    int  ans = 0;    while(x > 0){        ans += c[x];        x -= lowbit(x);    }    return ans;}

我们求SUM（L,R）只需要query(R) - query(L - 1)即可

 

【完整代码】

 

#include 
     
      using namespace std;const int maxn = 1e6+10; int  a[maxn];int n,m;int  c[maxn];void init(){    memset(a , 0 , sizeof a);    memset(c , 0 , sizeof c);}int lowbit(int x){    return x & (-x);}int  query(int x){    int  ans = 0;    while(x > 0){        ans += c[x];        x -= lowbit(x);    }    return ans;}void add(int x , int  val){    while(x <= n){        c[x] += val;        x += lowbit(x);    }}int main(){    while(cin>>n>>m){        init();        for(int i=1; i<=n; i++){            cin>>a[i];            add(i , a[i]);        }        int op,L,R,pos,X;        for(int i=1; i<=m; i++){            cin>>op;            //如果是查询操作             if(op == 1){                cin>>L>>R;                 cout<
      
       >pos>>X;                add(pos , X - a[pos] );                a[pos] = X;            }        }            }    return 0;}