概括

树状数组是个好东西啊~（代码量少orz）

简介

树状数组是用数据压缩的思想由二进制实现的数据结构。有单点修改+区间查询或区间修改+单点查询的作用。

实现单点修改&区间查询

首先我们来看看暴力的效率。q组询问，极端情况下n个数的修改，效率为 O(n q) 。n，q为500000时一定会炸。

切入点：lowbit函数

由于电脑一种叫做补码的操作（由于电脑是二进制，它们存的相反数是它的取反+1），一个数与它的相反数做与操作时会返回二进制下最右边的1的位置。举个例子： 6&-6=2 将6变成二进制：110。其中最右侧的1加粗字体：110则返回的是二进制下10的值：2。得到代码：

//ll就是long long
ll lowbit(ll num){
    return num&-num;
}

利用这个性质建立树状数组：

为了简化区间修改的效率，我们需要建立这样的一个数组：数组中第k位的值为原数组中的一段区间和，这个区间的长度是lowbit(k),终点是k。 比如：输入一个数组，那么我们所建立的数组：

第一位（1在二进制下=1 二进制下的1=1）的值为输入的数组的第一位往前的一位的和，也就是第一位。
第二位（2在二进制下=10 二进制下的10=2）的值为输入的数组的第二位往前两位的和，第一位和第二位。
第三位（3在二进制下=11 二进制下的1=1）的值为输入的数组的第三位往前一位的和，也就是第三位。
第四位的值（4在二进制下=100 二进制下的100=4）的值为输入的数组的第四位往前四位的和，也就是第一位，第二位，第三位以及第四位。
我们就称这种数组为树状数组

代码

void build(ll s,ll num){
    for(ll i=s;i<=n;i+=lowbit(i)) tree[i]+=num;//当s在i的范围内 第num位数组加上num 
}

跟着代码走一遍：

假设输入的n=5，输入的数为1 5 4 2 3（样例）
输入第一个数时s=1，num=1。加上的树状数组数组位数为第一位，第二位，第四位。树状数组为：1 1 0 1 0
输入第二个数时s=2，num=5，加上的位置为第二位，第四位。数组为1 6 0 6 0
输入第三个数时s=3，num=4，加上的位置为第三位。数组为1 6 4 10 0
输入第四个数时s=4，num=2，加上的位置为第四位。数组为1 6 4 12 0
输入第五个数时s=5，num=3，加上的位置为第五位。数组为1 6 4 12 3
至此，建树操作已经完成了。可以发现这个操作的本质就是修改树状数组的值，所以它也是单点修改的函数。

查询也是一样的。注意我们的操作不是区间求和，而是求两个前缀和的差！

//反着的建树。此操作是求输入的数据第1到第s位的和。

ll ask(ll s){
    ll ans=0;
    for(ll i=s;i>=1;i-=lowbit(i)) ans+=tree[i];//建树的反操作 
    return ans;
}

举一个sample（example） 求第三项和第五项之间的和。 本质上就是求5的前缀和与2的前缀和的差。（1 2 3 4 5）-（1 2）=（3 4 5）

先求5的前缀和。所求的就是第5（101）项+第4（100）项就是12+3=15。
再求2的前缀和。所求的就是第2（10）项就是6。
最后作差就是15-6=9。
检验一下，3到5位的求和就是4+2+3=9。没有问题！

把所有的结合起来就是树状数组啦~

代码

//树状数组代码 

#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
ll n,q,m,mod,x,y,tree[500001];
ll lowbit(ll num){
    return num&-num;//返回值为二进制下num从左往右第一个1的位置 
}
void build(ll s,ll num){
    for(ll i=s;i<=n;i+=lowbit(i)) tree[i]+=num;//当s在i的范围内 第num位数组加上num 
}
ll ask(ll s){
    ll ans=0;
    for(ll i=s;i>=1;i-=lowbit(i)) ans+=tree[i];//建树的反操作 
    return ans;
}
int main(){
    scanf("%lld%lld",&n,&q);
    for(int i=1;i<=n;i++){
        scanf("%lld",&m);
        build(i,m);//建立树状数组 
    }
    for(int i=1;i<=q;i++){
        scanf("%lld%lld%lld",&mod,&x,&y);//输入1或2 
        if(mod==1) build(x,y);//修改与建树可以共用一个函数 
        if(mod==2) printf("%lld\n",ask(y)-ask(x-1)/*思考为什么是x-1*/);//区间查询则为右边界前缀和减去左边界前缀和 
    }
}

其中的效率为 O（q logn） 。与 O（nq） 有着质的差别。

实现区间修改&单点查询

这看起来与单点修改&区间查询差不多，但实际上有很大的区别。如果我们按照原来的效率，得到的就是 O(n q) ，稳炸。

突破口：差分

思考一下，如果区间修改2到4位之后求第3位，我们就可以加上修改的数。而如果求第5位，我们只需要在第3位的基础上减去修改的数就可以了。举个例子：在数组第2位和第4位之间加上2，只需要将数组从0 0 0 0 0变成0 2 0 0 -2即可。当询问第3位时，答案就是输入的3的值+0+2+0即可。当询问5时，答案就是输入的5的值+0+2+0+0+-2=输入的5的值+0。这就是解法了！

代码

void add(ll s,ll num){
    chafen[s]+=num;//修改得到x,y,s时,只需要求add(x,s)和add(y,-s) 
}

如何让它再快一些呢？如果我们将我们刚刚打出来的树状数组来维护差分的这个数组，效率就达到最高啦~

void add(ll s,ll num){
    for(ll i=s;i<=n;i+=lowbit(i)) tree[i]+=num;//树状数组维护差分修改
}

查询

上文已经提过了，直接上代码~

ll ask(ll s){
    ll ans=0;
    for(ll i=s;i>=1;i-=lowbit(i)) ans+=tree[i];//寻找差分的标记 
    return ans;
}

最后的最后—代码

//树状数组代码 
#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
ll n,q,mod,x,y,s,inn[500001],tree[500001];
ll lowbit(ll num){
    return num&-num;//返回值为二进制下num从左往右第一个1的位置 
}
void add(ll s,ll num){
    for(ll i=s;i<=n;i+=lowbit(i)) tree[i]+=num;//差分的思想 
}
ll ask(ll s){
    ll ans=0;
    for(ll i=s;i>=1;i-=lowbit(i)) ans+=tree[i];//寻找差分的标记 
    return ans;
}
int main(){
    scanf("%lld%lld",&n,&q);
    for(int i=1;i<=n;i++) scanf("%lld",&inn[i]);
    for(int i=1;i<=q;i++){
        scanf("%lld",&mod);//输入1或2 
        if(mod==1){
            scanf("%lld%lld%lld",&x,&y,&s);
            add(x,s);
            add(y+1,-s);
        }
        if(mod==2){
            scanf("%lld",&x);
            printf("%lld\n",inn[x]+ask(x));//区间查询则为右边界前缀和减去左边界前缀和 
        }
    }
}

至此，树状数组算是完结啦~
参考文章：
https://www.luogu.com.cn/blog/64882/shu-zhuang-shuo-zu