树状数组模板

学个前缀和的进阶
致谢dalao

首先要知道lowbit :

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

操作一共就俩

单点更新

 //x为更新的位置,y为x要加的数,n为数组最大值
void update(int x,int y,int n){
    for(int i=x;i<=n;i+=lowbit(i))   
        c[i] += y;
}

区间查询

getsum得到前缀和

int getsum(int x){
    int ans = 0;
    for(int i=x;i;i-=lowbit(i))
        ans += c[i];
    return ans;
}
 

例题

---

第一题

#include <bits/stdc++.h>
#include <unordered_map>
using namespace std;
typedef long long ll;

#define lowbit(a) ((a)&-(a))
const int maxn =  5*1e4+5;
const int INF = 0x3f3f3f3f;

int c[maxn];
void update(int x,int y,int n){
    for(int i=x;i<=n;i+=lowbit(i))
        c[i] += y;
}
int getsum(int x){
    int ans = 0;
    for(int i=x;i;i-=lowbit(i))
        ans += c[i];
    return ans;
}
int main(){
    int t;
    int n;
    int x,y,z;
    string s;
    cin>>t;
    for (int i = 1; i <= t ; ++i) {//t是局数
        cin>>n;//n是每局队伍数
        memset(c,0,sizeof(int)*(n+1));

        cout <<"Case "<<i<<":"<<endl;
        for (int j = 1; j <= n ; ++j) {
            cin>>x;
            update(j,x,n);//本来就是0，初始化其实就是加
        }
        while(1){
            cin>>s;
            if(s[0]=='E')//检测字符串的第一个字母
                break;
            else if(s[0]=='Q'){
                cin>>y>>z;
                cout<<getsum(z)-getsum(y-1)<<endl;
            }
            else if(s[0]=='A'){
                cin>>y>>z;
                update(y,z,n);
            }
            else{
                cin>>y>>z;
                update(y,-z,n);//减就是+的负操作
            }
        }

    }

}

第二题

这篇稍微说一下
维护了一个新数组，初始值全为0
然后跟差分数组似的，如果 C l r d 就b[l]+d b[r+1]-d
然后返回的时候就是a[i]+b[i]
对b进行操作和查询的时候采用树状数组