P3368 树状数组2

FDOI · 2025-03-16 18:27:33 · 个人记录

思路：

这道题要求实现区间加和和单点查询，利用一般的树状数组可能不行，所以需要考虑修改。

修改：

考虑差分，差分可以实现区间修改功能，修改差分数组等于修改改数组所管辖的区间。

考虑将差分数组存入树状数组，此时单点修改等价于区间修改，区间查询等于单点查询。

思路不难，开始代码。

code：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m;
int a[8000001];
int c[2000001];
int sum[2000001];
int lowbit(int x){
    return x&(-x);
} 
void add(int x,int k){
    while(x<=n){
        c[x]+=k;
        x+=lowbit(x);
    }
}
int get(int x){
    int ans=0;
    while(x>0){
        ans+=c[x];
        x-=lowbit(x);
    }
    return ans;
}
signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>sum[i];    
        a[i]=sum[i]-sum[i-1];
        add(i,a[i]);    
    }
    for(int i=1;i<=m;i++){
        int opt;
        cin>>opt;
        int x,y,k;
        if(opt==1){
            cin>>x>>y>>k;
            add(x,k);
            add(y+1,-k);
        } 
        else{
            cin>>x;
            cout<<get(x)<<endl;
        }
    }
    return 0;
}