敌兵布阵(树状数组模板题)
程序员文章站
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;
}