线段树区间总和,单点更新。admin管理员组文章数量:1612098
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
const int maxN=100010;
int tree[4*maxN];
int money[maxN];
void build(int no,int l,int r)
{
if(l==r)
{
tree[no]=money[l];
return;
}
int mid=(l+r)>>1;
int no2=no<<1;
build(no2,l,mid);
build(no2+1,mid+1,r);
tree[no]=tree[no2]+tree[no2+1];
}
void update1(int no,int l,int r,int x)
{
if(l==r)
{
printf("%d\n",tree[no]);
tree[no]=0;
return;
}
int mid=(l+r)>>1;
int no2=no<<1;
if(x<=mid) update1(no2,l,mid,x);
else update1(no2+1,mid+1,r,x);
tree[no]=tree[no2]+tree[no2+1];
}
void update2(int no,int l,int r,int x,int change)
{
if(l==r)
{
tree[no]+=change;
return;
}
int mid=(l+r)>>1;
int no2=no<<1;
if(x<=mid) update2(no2,l,mid,x,change);
else update2(no2+1,mid+1,r,x,change);
tree[no]=tree[no2]+tree[no2+1];
}
int query(int no,int l,int r,int a,int b)
{
if(a==l && b==r)
{
return tree[no];
}
int mid=(l+r)>>1;
int no2=no<<1;
if(b<=mid) return query(no2,l,mid,a,b);
if(a>mid) return query(no2+1,mid+1,r,a,b);
return query(no2,l,mid,a,mid)+query(no2+1,mid+1,r,mid+1,b);
}
int main()
{
int t;
//freopen("stdin.txt","r",stdin);
scanf("%d",&t);
for(int id=1; id<=t; id++)
{
int n,m;
int cas;
int x,y;
printf("Case %d:\n",id);
scanf("%d %d",&n,&m);
for(int i=1; i<=n; i++)
scanf("%d",&money[i]);
build(1,1,n);
for(int i=1; i<=m; i++)
{
scanf("%d",&cas);
switch(cas)
{
case 1:
scanf("%d",&x);
x+=1;
update1(1,1,n,x);
break;
case 2:
scanf("%d %d",&x,&y);
x+=1;
update2(1,1,n,x,y);
break;
case 3:
scanf("%d %d",&x,&y);
x+=1,y+=1;
printf("%d\n",query(1,1,n,x,y));
break;
}
}
}
return 0;
}
版权声明:本文标题:LightOJ1112——Curious Robin Hood 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/dongtai/1728631199a1167105.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论