AcWing 242. 一个简单的整数问题

题目链接：https://www.acwing.com/problem/content/248/

思路

把树状数组改成差分数组，每次算差分后的一个数其实就是算前缀和

代码

#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug  freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define PI acos(-1)
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
using namespace std;

int N,M;
int arr[maxn],tr[maxn];

int lowbit(int x){
    return x & -x;
}
void add(int idx,int v){
    for(int i = idx;i<=N;i += lowbit(i)) tr[i] += v;
}
ll query(int r){
    ll sum = 0;
    for(int i = r;i>=1;i -= lowbit(i)) sum += tr[i];
    return sum;
}
int main(){
    ios;
    cin>>N>>M;
    for(int i = 1;i<=N;i++) cin>>arr[i];
    while(M--){
        string op;cin>>op;
        if(op == "Q"){
            int r;cin>>r;
            cout<<query(r) + arr[r]<<endl;
        }else{
            int l,r,d;cin>>l>>r>>d;
            add(l,d);
            add(r+1,-d);
        }
    }
    return 0;
}