特点

代码短、常数很小

应用及时间复杂度

1. 区间查询：求前缀和
2. 单点修改：给某个位置上的数加上一个数（同时能以非常小的代价维护前缀和）

时间复杂度：$O(logn)$

与一般前缀和算法的对比

可以看出在修改和查询操作占比差不多时，树状数组的效率更高

那么什么时候用树状数组，什么时候用一般前缀和算法呢？
这就要明白这两个算法的本质区别：
一般前缀和算法是离线算法，它不支持动态的改变单个元素的值，或者说改变单个元素值后，重新维护前缀和所花费的代价很大。
树状数组是在线算法，支持动态改变单个元素的值，以很小的代价动态维护前缀和。
所以当仅仅需要用到前缀和，不涉及动态的改变单个元素的值时，首选一般前缀和算法，否则就用树状数组。

树状数组原理

树状数组图例（下标从$1$开始）

假设原序列为$a$，树状数组序列为$c$,那么是怎么由原序列得到树状数组序列的呢？(可以把$c$理解为$a$的前缀和序列，只是前缀和关系不像一般前缀和那样简单、线性)
1. 首先，将一维的树状数组序列$c$看成多层的序列，$c[i]$属于第几层，取决于$i$的二进制表示中最后一个$1$后面有几个$0$，有几个$0$就在第几层，显而易见,当$i$为奇数时，$c[i]$是在第$0$层的
因为$lowbit(x)=2^{k}$,$k$表示x的二进制表示后面有多少个0
（$lowbit(n)$求得n的二进制表示中最后一个1以及往后的0）
可以得到关系：
$c[x]=a(x-lowbit(x),x]$
此关系描述了序列$c$中每个元素是哪一段序列$a$中元素的和
2. 如何通过树状数组求前缀和？
由上面公式知道，想要求序列$a$中$1$到$x$的和，则应该是：

$\sum_{i=1}^{x}a_i=c[x]+c[x-lowbit(x)]+......$
因而可得代码：

int res=0;
for(int i=x;i>0;i-=lowbit(x)) res+=c[i];
return res;

1. 如何通过树状数组进行单点修改？
   这里我们给出一个结论：一个结点$a[i]$或$c[i]$的父结点为$c[i+lowbit(i)]$
   所以当我们改变$a[i]$的值时，依次递归向上更新父结点的值即可。
   代码：

a[x]+=v;
for(int i=x;i<=n;i+=lowbit(i)) c[i]+=v;

我们发现这里是给某个数加上一个数$v$，而不是把某个数变成$v$，如果想实现这样的效果，该怎么做呢？
我们可以把加的数$v$灵活的调整为$v-x$（假设原来的数为$x$），加上$v-x$之后原来的数$x$就变成$v$了，从而实现了让一个数变成一个给定的数的效果。
获得原来的数的方式:
+ 树状数组前缀和相减：$c[x]-c[x-1]$
+ 开一个数组存原数组

树状数组只能给一个数加上一个数，而不能把一个数变成一个数，要实现这样的操作，作上面的变换即可。

初始化树状数组

可以假设原序列$a$为全0，依次通过“单点修改”操作把每个数加进去，最后就可以形成树状数组了。

例题：AcWing 1264. 动态求连续区间和

#include<iostream>
using namespace std;
const int N=100010;
int a[N],c[N];
int n,m;
int k,x,y;
int lowbit(int x)
{
    return x&(-x);
}
void add(int x,int v)
{
    for(int i=x;i<=n;i+=lowbit(i)) c[i]+=v;
}
int query(int x)
{
    int res=0;
    for(int i=x;i>0;i-=lowbit(i)) res+=c[i];
    return res;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++) add(i,a[i]);   //初始化

    while(m--)
    {
        scanf("%d%d%d",&k,&x,&y);
        if(k==0) printf("%d\n",query(y)-query(x-1));
        else add(x,y);
    }
    return 0;
}