【引言】假如我们有一个长度为N的数组，我们需要频繁地进行如下两种操作：
（1）修改下标为 i 的某个元素的值；
（2）查询下标 L 到 R的区间的元素和。
如果我们采用朴素的算法，很显然，操作1的时间复杂度是O（1），频繁修改一点问题没有，但是操作2的时间复杂度为O（R - L），试想一下，如果频繁地查询效率是极低的。比如说N = 108 查询次数M = 106，这样总的时间复杂度达到O（NM）1014，是根本不能忍受的。
【问题分析】首先我们分析一下采用朴素的算法它究竟慢在哪里。比如说我之前修改了a[7] 现在我要查询a[8] ~ a[10]，我每次查询区间和都要重新算一遍。那么我们可不可以把区间和事先存起来，存在另外一个数组 C[]中，这样我们在查询区间和的时候就直接O（1）地调用就好了。
存储任意L - R的区间和是不现实的，这个C数组要开成二维，空间占用1016。
【问题解决】有人提出来可以构造一个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] = 
那么Pi是Pi-1的值减去Pi-1最低位那一位的1所代表的的权值，直到Pi = 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 <bits/stdc++.h> 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<<query(R) - query(L-1)<<endl; } //如果是修改操作 else{ cin>>pos>>X; add(pos , X - a[pos] ); a[pos] = X; } } } return 0; }