欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

敌兵布阵(树状数组模板题)

程序员文章站 2024-03-03 16:18:58
...

敌兵布阵

题目传送门

敌兵布阵

题目大意

给你一个长度为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=5e5 +9;
int n, k;
int a[N],bit[N]; //对应原数组和树状数组

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

void updata(int i,int k){    //在i位置加上k
    while(i <= n){
        bit[i] += k;
        i += lowbit(i);
    }
}

int getsum(int i){        //求A[1 - i]的和
    int res = 0;
    while(i > 0){
        res += bit[i];
        i -= lowbit(i);
    }
    return res;
}

void sub(int i,int k)       //在i的位置上减k
{
    while(i<=n)
    {
        bit[i]-=k;
        i+=lowbit(i);
    }
}

void solve(){
    cin>>n;
    memset(bit,0,sizeof(bit));
    for(int i=1; i<=n; i++){
        cin>>a[i];
        updata(i,a[i]);
    }
    string Add="Add", Query="Query", Sub="Sub", End="End", s;
    k++;
    cout<<"Case "<<k<<":"<<endl;
    while(cin>>s && s!=End){
        int a, b;
        cin>>a>>b;
        if(s==Add)          updata(a,b);
        else if(s==Query)   cout<<getsum(b)-getsum(a-1)<<endl;
        else if(s==Sub)     sub(a,b);
    }
    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
    int T;
    cin>>T;
    while(T--)  solve();
    return 0;
}