树状数组是解决区间查询问题中非常简洁高效的数据结构，它可以使算法的时间复杂度降到O(logn)。
树状数组的问题模型
首先我们搞明白树状数组是用来干嘛的，现在有一个这样的问题：有一个数组a，下标从0到n-1，现在给你w次修改，q次查询，修改的话是修改数组中某一个元素的值；查询的话是查询数组中任意一个区间的和，w + q < 500000。
这个问题很常见，首先分析下朴素做法的时间复杂度，修改是O(1)的时间复杂度，而查询的话是O(n)的复杂度，总体时间复杂度为O(qn)；可能你会想到前缀和来优化这个查询，我们也来分析下，查询的话是O(1)的复杂度，而修改的时候修改一个点，那么在之后的所有前缀和都要更新，所以修改的时间复杂度是O(n)，总体时间复杂度还是O(qn)。
可以发现，两种做法中，要么查询是O(1)，修改是O(n)；要么修改是O(1)，查询是O(n)。那么就有没有一种做法可以综合一下这两种朴素做法，然后整体时间复杂度可以降一个数量级呢？有的，对，就是树状数组。
lowbit函数
这里我们先不管树状数组这种数据结构是什么，先来了解下lowbit这个函数
顾名思义，lowbit这个函数的功能就是求某一个数的二进制表示中最低的一位举个例子，x = 6，它的二进制为110，那么lowbit(x)就返回2，因为最后一位1表示2。
如何求lowbit？
把这个数的二进制写出来，然后从右向左找到第一个1(这个1就是我们要求的结果，但是现在表示不出来，后来的操作就是让这个1能表示出来)，这个1不要动和这个1右边的二进制不变，左边的二进制依次取反，这样就求出的一个数的补码，说这个方法主要是让我们理解一个负数的补码在二进制上的特征，然后我们把这个负数对应的正数与该负数与运算一下，由于这个1的左边的二进制与正数的原码对应的部分是相反的，所以相与一定都为0,；由于这个1和这个1右边的二进制都是不变的，因此，相与后还是原来的样子，故，这样搞出来的结果就是lowbit(x)的结果。
代码如下
int lowbit(x) {return x & -x;}
树状数组的思想
先定义一些东西：arr是原数组，c是新开的一个数组，这个数组代表后缀和(问题模型中是用的前缀和，这里要用后缀和，具体原因马上就知道了)；
二进制的视角：一个数n，假设n = 6，它的二进制为110，我们把它表示成累加的形式110 = 100 + 10，这样是可以的，那么我们要求前6(110)项的和是不是可以这样求：
ans= (arr1+arr2+arr3+arr4)+(arr5+arr6)
注意括号中的元素个数，是不是4(100)个加2(10)个，和110 = 100 + 10是不是很像，不知你们发现了吗，10就是lowbit(110)的结果，100是lowbit(100)的结果。求和的时候我们总是把1~n拆分成这样的几段区间和来计算，而如何去确定这些区间的起点和长度呢？就是根据n的二进制来的(不懂的可以再看下上面举的例子)，二进制怎么拆的，你就怎么拆分，而拆分二进制就要用到上面说的lowbit函数了。这里也可以顺理成章得给出c数组的表示了。
这里也可以顺理成章得给出c数组的表示了，c[i]表示从第i个元素向前数lowbit(i)个元素，这一段的和，这就是上面说的区间和，只不过这个区间是靠右端点的。其实你把所有的数字都看成二进制，很好理解的。
树状数组的实现
设计一种数据结构，需要的操作无非就是”增删改查“，这里只讨论查询和修改操作具体是怎么实现的；
查询
这里说的查询是查询任一区间的和，由于区间和具有可加减性，故转化为求前缀和；查询前缀和刚刚在树状数组的思想中已经说过了，就是把大区间分成几段长度不等的小区间，然后求和。区间的个数为O(logn)，所以查询的时间复杂度为O(logn)。
修改
修改某一位置上的元素的时间复杂度为O(1)，但是要更新c数组，不然查询的时间复杂度就会变高。更新的方法就要提一下树状数组的性质了和树状数组那张经典的图片了。
这张图片中已经把c数组的后缀和这个含义已经表达得很清楚了。这个时候你再把查询操作对应到这张图上，然后看着二进制来操作，是不是就可以很直白地理解上面所说的查询操作了！
我们从这张图中可以得到树状数组的如下性质：
后缀和的长度是2的幂；
上一层后缀和的长度是下一层后缀和长度的两倍；
下一层后缀和只要补上自己后缀和的长度就可以得到上面层的后缀和(图中的虚框框)，注意，是上面的后缀和，而不是上一层的后缀和，这个性质就是更新操作的依据；
最后一位1右边有多少个0(可以用log2(lowbit(x))表示)就表示这一层有多少个直系子层(子层的意思就是这一层的和包含下面某一层的和)。
更新的时候只要更新修改这个点会影响到的那些后缀和(c数组)，假设现在修改6(110)这个点，依据树状数组的性质三，它影响的直系父层就是c[6(110) + lowbit(6(110))] = c[8(1000)]，但是它肯定不是只影响直系父层，上面所有包含这一层和的层都要更新，但是我们把这个更新传递给直系父层c[8],8这个点的直系父层是c[16]，依次类推地更新就行了。
代码
查询前缀和
int sum(int x, ArrayInt c, int n){int ret = 0;for ( ; x > 0; ret += c[x], x -= lowbit(x));return ret;}
更新后缀和
void update(int x, int val, ArrayInt c, int n){for ( ; x <= n; c[x] += val, x += lowbit(x));}
用个例题来说明
题目描述
已知一个数列，你需要进行下面两种操作：
将某区间每一个数数加上 x；
求出某一个数的值。
输入格式
第一行包含两个整数 N、M，分别表示该数列数字的个数和操作的总个数。
第二行包含 N 个用空格分隔的整数，其中第 i个数字表示数列第 i项的初始值。
接下来 M 行每行包含 2 或 4个整数，表示一个操作，具体如下：
操作 1：格式：1 x y k 含义：将区间 [x,y]内每个数加上 k；
操作 2：格式：2 x 含义：输出第 x个数的值。
输出格式
对于每个操作2，输出第x个数的值
#include<bits/stdc++.h>#define lowbit(x) x & -xusing namespace std;long long tree[500005];int n, m;void add(int x, long long num) {while (x <= n) {tree[x] += num;x += lowbit(x);}}long long query(int x) {long long ans = 0;while (x) { ans += tree[x]; x -= lowbit(x); }return ans;}int main() {scanf("%d%d", &n, &m);long long last = 0, now;for (int i = 1; i <= n; i++) {scanf("%lld", &now);add(i, now - last);//差分处理last = now;}int flg;while (m--) {scanf("%d", &flg);if (flg == 1) {int x, y;long long k;scanf("%d%d%lld", &x, &y, &k);add(x, k);//差分处理add(y + 1, -k);} else if (flg == 2) {int x;scanf("%d", &x);printf("%lld\n", query(x));}}}
