A Simple Problem with Integers(树状数组)

发布于 2020-08-30  0 次阅读


题目大意:

给你一个长度为n的数组
进行m次操作,操作包括对区间的值进行加减和对区间进行求和

思路:

区间更新,区间查询的树状数组
考虑使用更加简单的树状数组,区间更新可以使用差分维护,区间查询可以开两个数组维护
int   sum1 [ N ] ;      / / ( D [ 1 ] + D [ 2 ] + . . . + D [ n ] )
int   sum2 [ N ] ;      / / ( 1 ∗ D [ 1 ] + 2 ∗ D [ 2 ] + . . . + n ∗ D [ n ] )

AC Code:

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
#define endl '\n'
#define INF 0x3f3f3f3f
#define int long long
// #define TDS_ACM_LOCAL
const int N=1e6 +9;
int n, m;
int a[N];
int sum1[N];    //(D[1] + D[2] + ... + D[n])
int sum2[N];    //(1*D[1] + 2*D[2] + ... + n*D[n])

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

void updata(int i,int k){
    int x = i;    //因为x不变,所以得先保存i值
    while(i <= n){
        sum1[i] += k;
        sum2[i] += k * (x-1);
        i += lowbit(i);
    }
}

int getsum(int i){        //求前缀和
    int res = 0, x = i;
    while(i > 0){
        res += x * sum1[i] - sum2[i];
        i -= lowbit(i);
    }
    return res;
}

void solve(){
    cin>>n>>m;
    for(int i = 1; i <= n; i++){
        cin>>a[i];
        updata(i,a[i] - a[i-1]);   //输入初值的时候,也相当于更新了值
    }
    while(m--){
        int x, y, k;
        string c;
        cin>>c;
        if(c=="Q"){
            cin>>x>>y;
            cout<<getsum(y)-getsum(x-1)<<endl;
        }
        else if(c=="C"){
            cin>>x>>y>>k;
            updata(x,k), updata(y+1,-k);
        }
    }
    return ;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
#ifdef TDS_ACM_LOCAL
    freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin);
    freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout);
#endif
    solve();
    return 0;
}

平平无奇的大学在读本科生