前言
学树状数组只图一乐，真学技术还得看线段树，但是图一乐还得图一乐，树状数组在时间复杂度(树状数组最坏情况是logn，但是线段树是所有情况都是nlogn，稍慢于树状数组) 和 空间复杂度(树状数组完胜于线段树，线段树要开2倍到4倍内存（推荐4倍），但是树状数组一倍就够了) 上还是更加优秀的，而且代码量也小的很多。
当然，线段树和树状数组，他们两个都能使对一个区间的数修改以及查询的速度提升许多。
而线段树的功能更加完善，对于算法比赛来说，学了树状数组是远远不够的，还是得在回去看看线段树。
先来模板吧，对于单点查询和区间修改和区间查询和单点修改这两种，代码模板是一样的，还有一种区间查询和区间修改类的题，由于出的不多，理解也没有那么简单，而且当你碰见的时候完全可以用线段树解决，我就在这里不多赘述。
inline int lowbit(int x){
return x&-x;
}
int query(int x){
int ans = 0;
while(x){
ans+=bit[x];
x-=lowbit(x);
}
return ans;
}
void add(int x,int y){
while(x<=n){
bit[x]+=y;
x+=lowbit(x);
}
}
这里牵扯到了一个知识点，就是叫做lowbit，lowbit是将一个二进制数的所有高位一都去掉，只留下最低位的1，比如lowbit（5）=lowbit（0101（二进制））=0001（二进制）这样就能维护树状数组（如图所示）
树状数组里的每一个位置存储的数不是你想象中的每一位就存每一位的数，而是像一棵树一样，有的位置存储的是两个数的和（比如位置2的地方），有的是四个数之和（比如位置4的地方），而lowbit操作恰好可以维护这种结构。
对于树状数组的详细讲解，入门可以看看b站的这个视频，如果实在难以理解，多敲几遍自然而然就记住了，常用慢慢也会理解，尤其是像树状数组的代码高度对称。
现在我来写一下第一种比较常见基础的：区间查询和单点修改
洛谷p3347
题目描述
如题，已知一个数列，你需要进行下面两种操作：
1.将某一个数加上x
2.求出某区间每一个数的和
输入格式
第一行包含两个整数N、M，分别表示该数列数字的个数和操作的总个数
第二行包含N个用空格分隔的整数，其中第i个数字表示数列第i项的初始值。
接下来M行每行包含3个整数，表示一个操作，具体如下：
操作1： 格式：1 x k 含义：将第x个数加上k
操作2： 格式：2 x y 含义：输出区间[x,y]内每个数的和
输出格式
输出包含若干行整数，即为所有操作2的结果。
输入输出样例
输入 #1
5 5
1 5 4 2 3
1 1 3
2 2 5
1 3 -1
1 4 2
2 1 4
输出 #1
14
16
对于这两种操作
询问区间和：
利用lowbit可以算出前缀和，求区间和调用两次求和做差。
单点修改：
利用lowbit计算出需要修改的C[i]，并进行更新。
更加细致的讲解在代码注释中
#include <bits/stdc++.h>
using namespace std;
int bit[500010],n;
inline int lowbit(int x){
return x&-x;
}
int query(int x){
int ans = 0;
while(x){
ans+=bit[x];
x-=lowbit(x);
}
return ans;
}
void add(int x,int y){
while(x<=n){
bit[x]+=y;
x+=lowbit(x);
}
}
int main(){
ios::sync_with_stdio(false);
int m,a,b,c;
cin>>n>>m;
for(int i = 1;i <= n;i++){
cin>>a;
add(i,a);//单点更新，当你输入每一个点的时候，就按照树状数组的添加方式来加点，i表示位置，a表示点的大
//小,这里还有个小技巧，就是你不必写单点减法的函数，你要加某个数add(i,a);，减某个数时就取负就行了，add(i,-a);
}
for(int i = 0;i < m;i++){
cin>>a>>b>>c;
if(a==1){
add(b,c); //同上
}
if(a==2){
int ans = query(c) - query(b-1); //query(c)这里的查询是查询的前c项之和，而器需要的是区间b到c的，那查询一次（0——c）区间，在查询一次（0——b-1）区间的，用前者减后者就是（b——c）区间的值了
cout<<ans<<"\n";
}
}
return 0;
}
当然，单点查询和区间修改不止可以用在简单的这里，你还可以去发挥自己的想象用到别的地方，这里有两道题可以做做，有助于学习理解 P1908 逆序对和HDU - 1556 Color the ball 而对于p1908这道题我在网上看到一篇很好的题解，也可以看看
下来就是进阶：单点查询和区间修改
在讲例题之前我先引进一个概念，叫做差分
这里有部分解释源于洛谷的大佬
设数组a[]={1,6,8,5,10}，那么差分数组b[]={1,5,2,-3,5}
也就是说b[i]=a[i]-a[i-1];(a[0]=0;)，那么a[i]=b[1]+…+b[i];(自己手写推一边就好了)。
当你看了这些，是不是感觉能和上面的操作结合起来，query操作就是求前n项的和，而当一个数组数据是按照差分数组存的，该数组 b[i] 前n项之和，正好就是原数组 a[i] 的第i项，由此实现了单点查询
然后，假如区间[2,4]都加上2的话
a数组变为a[]={1,8,10,7,10}，b数组变为b={1,7,2,-3,3};
发现了没有，b数组只有b[2]和b[5]变了，因为区间[2,4]是同时加上2的,所以在区间内b[i]-b[i-1]是不变的.
所以对区间[x,y]进行修改,只用修改b[x]与b[y+1]:
b[x]=b[x]+k;b[y+1]=b[y+1]-k;
由此，本来需要修改整个区间，现在只需要修改两个点就可以表示修改来了整个区间
区间更新，单点查询
用树状数组维护差分数组b[i]= a[i]-a[i-1] (b[1]=a[1])
单点查询a[i]：
树状数组计算b[1]到b[i]的前缀和就是a[i]
区间更新[L,R]：
只需更新b[L]和b[R+1],b[L]+=x,b[R+1]-=x
现在就来看看这道例题，解析在代码注释中
洛谷p3368
题目描述
如题，已知一个数列，你需要进行下面两种操作：
1.将某区间每一个数数加上x
2.求出某一个数的值
输入格式
第一行包含两个整数N、M，分别表示该数列数字的个数和操作的总个数。
第二行包含N个用空格分隔的整数，其中第i个数字表示数列第i项的初始值。
接下来M行每行包含2或4个整数，表示一个操作，具体如下：
操作1： 格式：1 x y k 含义：将区间[x,y]内每个数加上k
操作2： 格式：2 x 含义：输出第x个数的值
输出格式
输出包含若干行整数，即为所有操作2的结果。
输入输出样例
输入 #1
5 5
1 5 4 2 3
1 2 4 2
2 3
1 1 5 -1
1 3 5 7
2 4
输出 #1
6
10
#include <bits/stdc++.h>
using namespace std;
long long bit[500000+10],n;
inline int getbit(int x){
return x&-x;
}
long long qury(int x){
int ans;
while(x){
ans = ans + bit[x];
x -= getbit(x);
}
return ans;
}
void add(int x,int y){
while(x<=n){
bit[x]+=y;
x+=getbit(x);
}
}
int main(){
int m;
long long now,last = 0;
cin>>n>>m;
for(int i = 1;i <= n;i++){
cin>>now;
add(i,now-last);
last = now;//这两步操作使你的数组存进去就是按照差分数组的形式存储的，很好证明，有兴趣可以推一下
}
int f,l,r;
for(int i = 0;i < m;i++){
cin>>f;
if(f==1){
cin>>l>>r>>now;
add(l,now); //就像上面解释的，只需更改l位置和r位置
add(r + 1,-now);//所以这两句就实现了,和上一道题的区间查询有异曲同工之妙
}
else{
cin>>now;
cout<<qury(now)<<"\n";//单点查询直接输出
}
}
return 0;
}