线状数组是一个查询和复杂度都是log（n）的数据结构，主要用来查询任意两位之间的所有元素之和，但每次只能修改一个元素的值，
数组a[]— 用来存放原始数据，c[]–就是树状数组，c[t] – 表示t管辖区间元素之和。
c[t] --管辖里2^k个区间，k是t在二进制下末尾0的个数例如：8=（1000），那么管辖2³=8个数。例如5 = （101）那么管辖2⁰=1个数；
下面这个图非常直观；

如何计算t管辖的区间打下：（求t对应的2^k）;
下面两种皆可：

int lowbit(int x)
{return x&(x^(t-1));
}int lowbit(int x)
{return x&(-x);
}

n-lowbit(n) 将n二进制中最后一个（末尾）的1减去

点修改，区间查询

#include <bits/stdc++.h>
using namespace std;int n,m;
int a[50005],c[50005]; //对应原数组和树状数组int lowbit(int x){return x&(-x);
}void updata(int i,int k){    //在i位置加上kwhile(i <= n){c[i] += k;i += lowbit(i);}
}int getsum(int i){        //求A[1 - i]的和int res = 0;while(i > 0){res += c[i];i -= lowbit(i);}return res;
}int main(){int t;cin>>t;for(int tot = 1; tot <= t; tot++){cout << "Case " << tot << ":" << endl;memset(a, 0, sizeof a);memset(c, 0, sizeof c);cin>>n;for(int i = 1; i <= n; i++){cin>>a[i];updata(i,a[i]);   //输入初值的时候，也相当于更新了值}string s;int x,y;while(cin>>s && s[0] != 'E'){cin>>x>>y;if(s[0] == 'Q'){    //求和操作int sum = getsum(y) - getsum(x-1);    //x-y区间和也就等于1-y区间和减去1-(x-1)区间和cout << sum << endl;}else if(s[0] == 'A'){updata(x,y);}else if(s[0] == 'S'){updata(x,-y);    //减去操作，即为加上相反数}}}return 0;
}

区间更新，单点查询；

int n,m;
int a[50005] = {0},c[50005]; //对应原数组和树状数组int lowbit(int x){return x&(-x);
}void updata(int i,int k){    //在i位置加上kwhile(i <= n){c[i] += k;i += lowbit(i);}
}int getsum(int i){        //求D[1 - i]的和，即A[i]值int res = 0;while(i > 0){res += c[i];i -= lowbit(i);}return res;
}int main(){cin>>n;27     for(int i = 1; i <= n; i++){cin>>a[i];updata(i,a[i] - a[i-1]);   //输入初值的时候，也相当于更新了值}//[x,y]区间内加上kupdata(x,k);    //A[x] - A[x-1]增加kupdata(y+1,-k);        //A[y+1] - A[y]减少k//查询i位置的值int sum = getsum(i);return 0;
}

区间修改，区间查询

int n,m;
int a[50005] = {0};
int sum1[50005];    //(D[1] + D[2] + ... + D[n])
int sum2[50005];    //(1*D[1] + 2*D[2] + ... + n*D[n])int lowbit(int x){return x&(-x);
}void updata(int i,int k){int x = i;    //因为x不变，所以得先保存i值while(i <= n){sum1[i] += k;sum2[i] += k * (x-1);i += lowbit(i);}
}int getsum(int i){        //求前缀和int res = 0, x = i;while(i > 0){res += x * sum1[i] - sum2[i];i -= lowbit(i);}return res;
}int main(){cin>>n;for(int i = 1; i <= n; i++){cin>>a[i];updata(i,a[i] - a[i-1]);   //输入初值的时候，也相当于更新了值}//[x,y]区间内加上kupdata(x,k);    //A[x] - A[x-1]增加kupdata(y+1,-k);        //A[y+1] - A[y]减少k//求[x,y]区间和int sum = getsum(y) - getsum(x-1);return 0;
}

代码来源