数组：
求前缀和是 O(n)，修改某个数是O(1)；
前缀和数组：
求前缀和是 O(1)，修改某个数是O(n)；

树状数组可以保证把这两类的复杂度都变为 O(logn) ；

树状数组的性质：
1.每个内部结点c[x]保存以它为根的子树中所有叶节点的和。
2.每个内部结点c[x]的子节点个数等于lowbit(x)的位数。
3.除树根外，每个内部结点c[x]的父节点是c[x+lowbit(x)]。
4.树的深度为O(logN)。

划分区间：

while(x>0)
{
    printf("[%d,%d]\n",x-(x& -x)+1,x);
    x-=x& -x;
}

对于序列a,建立一个数组c，其中c[x]保存序列a的区间[x-lowbit(x)+1,x]中所有数的和，
则得到区间求和函数：

int ask(int x)
{
    int ans=0;
    for(;x;x-=(x&-x)) ans+=c[x];
    return ans;
}

单点修改：

void add(int x,int y)
{
    for(; x<=N; x+=(x& -x) ) c[x]+=y;
}

//其中，y是增加的数值，N是数组长度（数据个数）。

初始化，对数组中的每一个数进行add操作。

树状数组和逆序对:
任意给定集合a，可以建立树状数组t来保存a数值中出现的次数，则区间和t[l,r]代表集合a中值域在[l,r]中的数有多少个。

通过这个方法，再配合逆序扫描，我们可以再O((N+M)logN)中扫描出数组中逆序对的数量。（M为数据范围的大小）。

1.在序列a的数值范围上建立树状数组，初始化为全0.
2.倒序扫描给定的序列a，对于每个数a[i]：
1）在树状数组中查询前缀和[1,a[i]-1]，累加到答案ans中。
2）之星“单点增加操作，
3.ans即为所求。

拓展应用：
区间修改，单点查询。
建立树状数组，用来维护指令的累积影响。即l到r上都加x，相当于，l加x，r-=x；对于每个数，求前缀和之后，指令的影响和此前缀和是等价的。
查询时只需把本位的树状数组前缀和都求出来，然后在加上原来的数值a[i]即是当前所有修改之后的数值。
https://www.acwing.com/solution/content/23510/