HDU 1166(敌兵布阵)(树状数组 单点更新区间求和)
- #include<iostream>
- #include<cstring>
- #include<cmath>
- using namespace std;
- #define lowbit(x) x & (-x)//lowbit 函数
- #define LL long long
- LL a[100005],n;
- void updata(LL x,LL v) {// 更新函数
- while(x<=n) {
- a[x]+=v;
- x+=lowbit(x);
- }
- }
- LL query(LL x) {// 查询函数
- LL sum=0;
- while(x) {
- sum+=a[x];
- x-=lowbit(x);
- }
- return sum;
- }
- int main() {
- LL t;
- cin>>t;
- LL d=1;
- while(t--) {
- cout<<"Case"<<d<<":"<<endl;
- cin>>n;
- LL s;
- memset(a,0,sizeof(a));
- for(LL i=1; i<=n; i++) {
- cin>>s;
- updata(i,s);
- }
- string ss;
- int l,r;
- while(cin>>ss)
- {
- if(ss=="End"){
- break;
- }
- cin>>l>>r;
- if(ss[0]=='A') {
- updata(l,r);
- } else if(ss[0]=='S') {
- updata(l,-r);
- } else {
- cout<<query(r)-query(l-1)<<endl;
- }
- }
- d+=1;
- }
- return 0;
- }
- View Code
来源: http://www.bubuko.com/infodetail-2824186.html