树状数组

树状数组

点修改区间查询

P3374 【模板】树状数组 1
1.将某一个数加上x
2.求出某区间每一个数的和

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = -1e9;
const ll N =5e5+7;
const ll mod=1e9+7;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar(); return s * w; }
inline void write(ll x) { if (!x) { putchar('0'); return; } char F[200]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-'); int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';     tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;   while (b) { if (b & 1)  ans *= a;b >>= 1;a *= a; }   return ans; }   ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
ll getinv(ll x){return qpow(x,mod-2,mod);}
int n,a[N],m;
inline int lowbit(int x){
    return x&-x;
}
void add(int i,int val){
    while(i<=n){
        a[i]+=val;
        i+=lowbit(i);
    }
}
int sum(int i){
    int sum=0;
    while(i>0){
        sum+=a[i];
        i-=lowbit(i);
    }
    return sum;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        int val=read();
        add(i,val);
    }
    for(int i=1;i<=m;i++){
        int op,l,r;
        scanf("%d",&op);
        if(op==1){
            int pos,val;
            scanf("%d%d",&pos,&val);
            add(pos,val);
        }
        else if(op==2){
            int l,r;
            scanf("%d%d",&l,&r);
            printf("%d\n",sum(r)-sum(l-1));    
        }
    }
    return 0;
}

区间修改，区间查询

1.将某区间每一个数数加上x；
2.求出某一个数的值。
P3368 【模板】树状数组 2

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = -1e9;
const ll N =5e5+7;
const ll mod=1e9+7;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar(); return s * w; }
inline void write(ll x) { if (!x) { putchar('0'); return; } char F[200]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-'); int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';     tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;   while (b) { if (b & 1)  ans *= a;b >>= 1;a *= a; }   return ans; }   ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
ll getinv(ll x){return qpow(x,mod-2,mod);}
ll n,a[N],m;
inline int lowbit(int x){
    return x&-x;
}
void add(int i,int val){
    while(i<=n){
        a[i]+=val;
        i+=lowbit(i);
    }
}
int sum(int i){
    int sum=0;
    while(i>0){
        sum+=a[i];
        i-=lowbit(i);
    }
    return sum;
}
int main(){
    cin>>n>>m;
    ll last=0,now;
    for(int i=1;i<=n;i++){
        now=read();
        add(i,now-last);
        last=now;
    }
    for(int i=1;i<=m;i++){
        int op;
        scanf("%d",&op);
        if(op==1){
            int l,r,k;
            scanf("%d%d%d",&l,&r,&k);
            add(l,k);
            add(r+1,-k);
        }
        else if(op==2){
            int k;
            scanf("%d",&k);
            printf("%lld\n",sum(k));
        }
    }
    return 0;
}