这里有个视频讲的挺明白的。

‍

树状数组本身就是线段树的简化，所以树状数组能做的线段树都能做，但树状数组的空间复杂度是$O(n)$明显优于线段树，再加上写起来十分方便，所以一般能用树状数组的都不用线段树。

‍

最朴素树状数组支持单点修改和查询区间和，做个差分后还可以支持区间修改和查询单点值，根据题目需要还可以维护其他支持的操作。

思想

线段树中有许多节点（每层的第偶数个）实际上是多余的，可以通过大数组减小数组来达到效果。将这些多余的数删去就会发现剩下的数据正好有$n$个，用一个数组存下来就是树状数组。求和时找到对应区间相加即可，修改时从下往上修改。

‍

树状数组最核心的函数是就是lowbit函数：

ll lowbit(ll x){
    return x&(-x);
}

作用为求出一个二进制数字的最低位代表哪个数字，如$1000110$的$lowbit$就是$2$。然后就会发现序号为i的序列正好就是长度为$lowBit(i)$且以i结尾的序列。

于是求区间和就很简单了：

ll query(ll x){
    ll res=0;
    while(x){
        res+=a[x];
        x-=lowbit(x);
    }
    return res;
}

还有个很方便的性质就是$b[i]$正上方的序列正好就是$b[i+lowbit(i)]$，这样一看修改也很简单了：

void add(ll x,ll val){
    while(x<=n){
        a[x]+=val;
        x+=lowbit(x);
    }
    return ;
}

题

【模板】树状数组 1

板子题。

$AC Code:$

#include<iostream>
#include<queue>
#include<deque>
#include<bitset>
#include<string>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<unordered_map>
#include<set>
#include<map>
#include<ctime>
#include<random>
#include<vector>
#include<utility>
#define f(i,a,b) for(ll i=a;i<=b;i++)
using ll = long long;
using db = double;
ll rd(){ll x=0,w=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-'){w=-1;}c=getchar();}while('0'<=c&&c<='9'){x=x*10+(c-'0');c=getchar();}return x*w;}
using namespace std;
const int MX =5e5+7;
const ll mod = 1e9+7;
mt19937 mrd(time(0));
namespace Wunsch{

    ll a[MX];
    ll n,T,k,m,ans,cnt;

    string s;

    ll lowbit(ll x){
        return x&(-x);
    }

    void add(ll x,ll val){
        while(x<=n){
            a[x]+=val;
            x+=lowbit(x);
        }
        return ;
    }

    ll query(ll x){
        ll res=0;
        while(x){
            res+=a[x];
            x-=lowbit(x);
        }
        return res;
    }


    void work(){
        n=rd();m=rd();
        f(i,1,n){
            add(i,rd());
        }
        while(m--){
            int op=rd();
            ll x=rd();
            ll y=rd();
            if(op==1){
                add(x,y);
            }
            else {
                cout<<query(y)-query(x-1)<<endl;
            }
        }

        return ;
    }

    bool main(){
        // T=rd();
        T=1;
        while(T--){
            work();
        }
        return 1;
    }
}
bool amiya=Wunsch::main();
int main(){;}

【模板】树状数组 2

差分一下，还是板子题。

#include<iostream>
#include<queue>
#include<deque>
#include<bitset>
#include<string>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<unordered_map>
#include<set>
#include<map>
#include<ctime>
#include<random>
#include<vector>
#include<utility>
#define f(i,a,b) for(ll i=a;i<=b;i++)
using ll = long long;
using db = double;
ll rd(){ll x=0,w=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-'){w=-1;}c=getchar();}while('0'<=c&&c<='9'){x=x*10+(c-'0');c=getchar();}return x*w;}
using namespace std;
const int MX =5e5+7;
const ll mod = 1e9+7;
mt19937 mrd(time(0));
namespace Wunsch{

    ll a[MX];
    ll n,T,k,m,ans,cnt;

    string s;

    ll lowbit(ll x){
        return x&(-x);
    }

    void add(ll x,ll val){
        while(x<=n){
            a[x]+=val;
            x+=lowbit(x);
        }
        return ;
    }

    ll query(ll x){
        ll res=0;
        while(x){
            res+=a[x];
            x-=lowbit(x);
        }
        return res;
    }


    void work(){
        n=rd();m=rd();
        ll x,y;
        f(i,1,n){
            if(i==1){
                x=rd();
                add(i,x);
            }
            else {
                y=rd();
                add(i,y-x);
                x=y;
            }
        }
        while(m--){
            int op=rd();
            if(op==1){
                x=rd();
                y=rd();
                k=rd();
                add(x,k);
                add(y+1,-k);
            }
            else {
                x=rd();
                cout<<query(x)<<endl;
            }
        }

        return ;
    }

    bool main(){
        // T=rd();
        T=1;
        while(T--){
            work();
        }
        return 1;
    }
}
bool amiya=Wunsch::main();
int main(){;}

P1438 无聊的数列

做二阶差分，然后维护前缀和$d2\*{i}$和$d2\*{i} \times i$就好了。

发现有篇题解跟我思想一样写的还详细，懒得详细写了直接贴个link。

$AC Code:$

#include<iostream>
#include<queue>
#include<deque>
#include<bitset>
#include<string>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<unordered_map>
#include<set>
#include<map>
#include<ctime>
#include<random>
#include<vector>
#include<utility>
#define f(i,a,b) for(ll i=a;i<=b;i++)
using ll = long long;
using db = double;
ll rd(){ll x=0,w=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-'){w=-1;}c=getchar();}while('0'<=c&&c<='9'){x=x*10+(c-'0');c=getchar();}return x*w;}
using namespace std;
const int MX =5e5+7;
const ll mod = 1e9+7;
mt19937 mrd(time(0));
namespace Wunsch{

    ll a[MX], c[MX];
    ll n,T,k,m,ans,cnt;

    ll lowbit(ll x){
        return x&(-x);
    }

    void add(ll x,ll val){
        ll ooo=x;
        while(x<=n){
            a[x]+=val;
            c[x]+=val*ooo;
            x+=lowbit(x);
        }
        return;
    }

    ll query(ll x){
        ll res=0;
        ll ooo=x;
        while(x){
            res+=a[x]*(ooo+1)-c[x];
            x-=lowbit(x);
        }
        return res;
    }

    ll b[MX];

    void work(){
        n=rd();m=rd();
        ll x,y;
        f(i,1,n){
            b[i]=rd();
        }
        for(ll i=n;i>=2;i--){
            b[i]=b[i]-b[i-1];
        }
        for(ll i=n;i>=2;i--){
            b[i]=b[i]-b[i-1];
            add(i,b[i]);
        }
        add(1,b[1]);
        // f(i,1,n){
        //     cout<<b[i]<<" ";
        // }
        // cout<<endl;
        while(m--){
            int op=rd();
            if(op==1){
                ll L=rd(),R=rd(),K=rd(),D=rd();
/*
k k+d k+2d k+3d  0     0
k d   d    d     -k-3d 0
k d-k 0    0     -k-4d k+3d
*/
                add(L,K);
                add(L+1,D-K);
                add(R+1,-K-(R-L+1)*D);
                add(R+2,K+(R-L)*D);
        // f(i,1,n){
        //     ans=0;
        //         f(j,1,i){
        //             ans+=query(j);
        //         }
        //         cout<<ans<<endl;
        // }
            }
            else {
                x=rd();
                // ans=0;
                // f(i,1,x){
                    // ans+=query(i);
                // }
                cout<<query(x)<<endl;
            }
        }
        return ;
    }
    bool main(){
        // T=rd();
        T=1;
        while(T--){
            work();
        }
        return 1;
    }
}
bool amiya=Wunsch::main();
int main(){;}

（注释有点乱，懒得删了）