原文博客链接：https://www.cnblogs.com/acgoto/p/8583952.html
对于学习的线段树方面的，发现很多问题可以用它来求解，但是做题的时候发现，用线段树太容易tle也，很多次也是卡时间过的，然后就发现了树状数组。
首先我们搞明白树状数组是用来干嘛的，树状数组是一个查询和修改复杂度都为log(n)的数据结构。主要用于查询任意两位之间的所有元素之和，但是每次只能修改一个元素的值，经过简单修改可以在log(n)的复杂度下进行范围修改，但是这时只能查询其中一个元素的值(如果加入多个辅助数组则可以实现区间修改与区间查询)。
所以说，树状数组的求解和线段树的求解有些重合，但是功能没有线段树的那么广泛。但是对树状数组来说，其思想大概是用二进制的方法来实现。
先简单介绍下基本二进制的使用方法：
& 按位与 如果两个相应的二进制位都为1，则该位的结果值为1，否则为0
| 按位或 两个相应的二进制位中只要有一个为1，该位的结果值为1
^ 按位异或 若参加运算的两个二进制位值相同则为0，否则为1
~ 取反 ~是一元运算符，用来对一个二进制数按位取反，即将0变1，将1变0
<< 左移 用来将一个数的各二进制位全部左移N位，右补0 （<<1则是乘2）
>> 右移 将一个数的各二进制位右移N位，移到右端的低位被舍弃，对于无符号数，高位补0（>>1则是除2）
原理：lowbit
lowbit这个函数的功能就是求某一个数的二进制表示中最低的一位1，举个例子，x = 6，它的二进制为110，那么lowbit(x)就返回2，因为最后一位1表示2。
那么怎么求lowbit呢？把这个数的二进制写出来，然后从右向左找到第一个1(这个1就是我们要求的结果，但是现在表示不出来，后来的操作就是让这个1能表示出来)，这个1不要动和这个1右边的二进制不变，左边的二进制依次取反，这样就求出的一个数的补码，说这个方法主要是让我们理解一个负数的补码在二进制上的特征，然后我们把这个负数对应的正数与该负数与运算一下，由于这个1的左边的二进制与正数的原码对应的部分是相反的，所以相与一定都为0,；由于这个1和这个1右边的二进制都是不变的，因此，相与后还是原来的样子，故，这样搞出来的结果就是lowbit(x)的结果。
自己来理解一下是怎么存的数据到c数组里面
#include <stdio.h>
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <string>
#include <cstring>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <ctime>
#include <vector>
#include <fstream>
#include <list>
#include <iomanip>
#include <numeric>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define me0 memset(s,0,sizeof(s))
#define me1 memese(s,1,sizeof(s))
const int inf = 0x3f3f3f3f;
const int N=100005;
int a[N],b[N],c[N];
int lowbit(int x){
return x&(-x);
}
void update(int i,int cc,int n){
while(i<=n){
c[i]+=cc;
i+=lowbit(i);
}
}
int main(int argc, char * argv[])
{
std::ios::sync_with_stdio(false);
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
update(i,a[i],n);
}
for(int i=1;i<=n;i++) cout<<c[i]<<" ";
return 0;
}
输入：
5
1 2 3 4 5
运行结果：
1 3 3 10 5
结合图一起看，
c[1]=1,
c[2]=a[1]+a[2]=3
c[3]=a[3]=3
c[4]=a[1]+a[2]+a[3]+a[4]=10
c[5]=a[5]=5
然后后面的看到大佬的博客就直接贴个博客链接了，感觉大佬讲解的很详细了。
贴个大佬的模板：
int lowbit(int i){
return i & -i;
}
//-i 代表i的负数 计算机中负数使用对应的正数的补码来表示
例如 : i=6（0110） 此时 k=1
-i=-6=(1001+1)=(1010)
i&(-i)=(0010)=2=2^1
void update(int x,int cc,int n){
for(int i=x;i<=n;i+=lowbit(i)) //x为更新的位置,cc为更新后的数,n为数组最大空间
c[i]+=cc;
}
int sum(int x){ //求区间[1,x]内所有元素的和
int ans=0;
for(int i=x;i;i-=lowbit(i))
ans+=c[i]; // 从右往左累加求和
return ans;
}
来题模板题目 hdu1166
#include<bits/stdc++.h>
using namespace std;
int c[50004];
int lowbit(int i){
return i&(-i);
}
void update(int x,int cc,int n){
for(int i=x;i<=n;i+=lowbit(i)) //x为更新的位置,cc为更新后的数,n为数组最大空间
c[i]+=cc;
}
int sum(int x){ //求区间[1,x]内所有元素的和
int ans=0;
for(int i=x;i;i-=lowbit(i))
ans+=c[i]; // 从右往左累加求和
return ans;
}
int main(){
ios::sync_with_stdio(false);
int t,x,y,a;
char s[10];
cin>>t;
for(int z=1;z<=t;z++){
memset(c,0,sizeof(c));
int n,a;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a;
update(i,a,n);
}
cout<<"Case "<<z<<":"<<endl;
while(1){
cin>>s;
if(s[0]=='E') break;
cin>>x>>y;
if(s[0]=='A'){
update(x,y,n);
}
if(s[0]=='S'){
update(x,-y,n);
}
if(s[0]=='Q'){
cout<<sum(y)-sum(x-1)<<endl;
}
}
}
return 0;
}