树状数组
树状数组将数组分成树状结构存储信息，与线段树相似。代码短，但实现有局限性，功能较为单一。
树状数组将一些数组存区间和，一个例子如下：
维护如下序列：$1,2,3,1,6,2,5,1$。
<---------21---------->
<----7----> |
<-3-> | <-8-> |
<1> | <3> | <6> | <5> |
1 2 3 1 6 2 5 1
1 2 3 4 5 6 7 8树状数组：在保证数据不丢失的情况下，尽量多的存储信息。
这样我们可以向线段树的区间查询一样，直接查询区间和。例如查询 $[3,5]$ 的区间和，那么可以 $[1,5]-[1,2]=[1,4]+[5,5]-[1,2]$。而我们的区间查询复杂度为 $O(\log_n)$ ，即使一次询问要两次查询也很快。
维护区间信息，不难发现如果更新一个值，那么要更新所有覆盖这个数的区间的值（和线段树的节点更新一个道理）
区间处理
关于下标的二进制关系图如下：
1000
100 |
010 | 110 |
001 | 011 | 101 | 111 |
1 2 3 4 5 6 7 8看到二进制化的下标后，不难发现区间和存的数是所有当前位 $1$ 出现前的情况。例如 $4(100)$ 包含 $001,010,011$ 第三位（从左向右数） $1$ 出现前所有可能的三种情况，
同样，由于 $5$ 的第三位是 $1$，所以它不会存 $4$ 下标的值。在询问时也要分找区间加和，例如求 $[1,5]=[1,4]+[5,5]$ （ 这里的区间是为了好理解，在树状数组中可以直接 $[4]+[5]$ 即可）。
上传，下放实现
int l_b(int k){//快速上下访问（二进制）
return k&(-k);
}那么，为什么这么写？
首先一个数的补码是这个数的负数的二进制数。（补码是反码 $+1$，反码是原码（二进制）所有位的取反 $1$->$0$，$0$->$1$）
我们以 $8$ 二进制数来举例。
$5$：$00000101$
$-5$：$11111011$
当 $5\&-5$ 时，我们的找到了 $00000001$，将 $5$ 减去它。
$4$：$00000100$
$-4$：$11111100$
当 $4\&-4$ 时，我们的找到了 $00000100$，将 $4$ 减去它。
这正好是我们需要查询的区间！为什么呢？
我们先查的是区间 $[5,5]$ 然后减去 $1$，后查询的是
即 $[1,4]$，统计即可。
我们从概念出发：
补码是原码的反码 $+1$。反码是原码每位取反，如果这一位是 $1$，那么现在它是 $0$，我们给它 $+1$，可以更具它二进制特性，直接填好从右向左的第一个 $0$，而填的这个 $0$，正是原码中从右向左的第一个 $1$，我们已经知道这个 $1$ 之前的所有情况已经存储，我们直接拿来用即可，然后将这个 $1$ 拿去，前面的 $1$ 的情况也已经存过，直接加和，这样每次询问相当于求了这个数中有多少个 $1$ 的次数。
而修改数值（上传）也是一个道理，可以感性理解为不断左移最低位的 $1$，如果和原来位的 $1$ 重合，那么直接进位即可。
树状数组 1
代码
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<vector>
using namespace std;
long long r_r(){//快读
long long k=0,f=1;
char c=getchar();
while(!isdigit(c)){
if(c=='-')f=-1;
c=getchar();
}
while(isdigit(c)){
k=(k<<1)+(k<<3)+(c^48);
c=getchar();
}
return k*f;
}
const int o_o=5e5+10;
int n,m;
int t_r[o_o];//树状数组
int l_b(int k){//快速上下访问（二进制）
return k&(-k);
}
void b_t(int x,int k){//上传标记
while(x<=n){
t_r[x]+=k;//更新区间
x+=l_b(x);
}
}
int g_a(int k){//向下求和
int a_s=0;
while(k){
a_s+=t_r[k];//累计结果
k-=l_b(k);
}
return a_s;
}
int main(){
n=r_r();m=r_r();
for(int i=1;i<=n;i++){
int x=r_r();//读入原始序列值
b_t(i,x);//建树（更新区间信息）
}
while(m--){//操作
int op=r_r(),x=r_r(),y=r_r();
if(op==1)b_t(x,y);//更新区间（单点修改）
if(op==2){printf("%d",g_a(y)-g_a(x-1));//区间和
}
return 0;
} 树状数组 2
将区间加变成标记打在树状数组上，区间和变成了打标记的方法，查询向上查，存值向下找。区间存值时，区间的覆盖范围，就是这个区间增的值，但是由于树状数组的区间范围比较死板，所以如果覆盖的超过需求要在往下找，打一个相反数的标记，这样查询的时候，一正一反，直接抵消。
代码
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<vector>
using namespace std;
long long r_r(){//快读
long long k=0,f=1;
char c=getchar();
while(!isdigit(c)){
if(c=='-')f=-1;
c=getchar();
}
while(isdigit(c)){
k=(k<<1)+(k<<3)+(c^48);
c=getchar();
}
return k*f;
}
const int o_o=5e5+10;
long long t_r[o_o],a_a[o_o];
int n,m;
int l_b(int k){
return k&-k;
}
void a_d(int l,int r,int v){
while(r){//[1,r] 加标记
t_r[r]+=v;
r-=l_b(r);
}
l--;
while(l){//[1,l-1] 减去多打的标记
t_r[l]-=v;
l-=l_b(l);
}
return ;
}
void g_a(int k){
int a_k=a_a[k];//存储原序列中的值
long long a_s=0;
while(k<=n){//累计本数上的所有标记
a_s+=t_r[k];
k+=l_b(k);
}
printf("%lld\n",a_k+a_s);//标记加值为答案
return ;
}
int main(){
n=r_r(),m=r_r();
for(int i=1;i<=n;i++)a_a[i]=r_r();//存储原序列
while(m--){
int op=r_r(),x=r_r();
if(op==1){
int y=r_r(),v=r_r();
a_d(x,y,v);//区间标记
}else g_a(x);//找答案
}
return 0;
}个人感觉树状数组比较单一，不因为树状数组不学线段树。虽然代码短，但其他方面线段树更加灵活，思路难度相似。
