常州Day3

树状数组

写起来十分方便，代码量相较线段树小得多，时空复杂度低
支持：
单点修改，区间查询
洛谷P3374 树状数组1

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int n,m,a[N],c[N];
int low(int x){
    return x&-x;
}
void add(int x,int k){
    while(x<=n){
        c[x]+=k;
        x+=low(x);
    }
}
int find(int x){
    int sum=0;
    while(x){
        sum+=c[x];
        x-=low(x);
    }
    return sum;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        add(i,a[i]);
    }
    for(int i=1;i<=m;i++){
        int a1;
        cin>>a1;
        if(a1==1){
            int x,k;
            cin>>x>>k;
            add(x,k);
        }else{
            int x,y;
            cin>>x>>y;
            cout<<find(y)-find(x-1)<<endl;
        }
    }
    return 0;
}

区间修改，单点查询
洛谷P3368 树状数组2

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int n,m,a[N],t[N];
int low(int x){
    return x&-x;
}
void add(int x,int k){
    while(x<=n){
        t[x]+=k;
        x+=low(x);
    }
}
int find(int x){
    int sum=0;
    while(x){
        sum+=t[x];
        x-=low(x);
    }
    return sum;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        add(i,a[i]-a[i-1]);//用树状数组维护一个差分数组的前缀和
    }
    for(int i=1;i<=m;i++){
        int a1;
        cin>>a1;
        if(a1==1){
            int x,y,k;
            cin>>x>>y>>k;
            add(x,k);
            add(y+1,-k);
        }else{
            int x;
            cin>>x;
            cout<<find(x)<<endl;
        }
    }
    return 0;
}