首页 > 代码库 > 线段树之单点更新求和hdoj1166
线段树之单点更新求和hdoj1166
题目:hdoj1166
分析:题意很清晰,就是让你给某个点又增加或者减少x个,然后求某一段有多少个,我是用一个father数组保存叶子节点的编号,然后直接从当前节点开始,更轻到root就ok。
查询的话,从根节点开始,看在左子区间还是右子区间,直接查询到某一段全部在要查询的区间内,求和就ok,很简单。
代码:
#include <cstdio> #include <string> #include <iostream> using namespace std; const int N = 55000; struct Node { int l,r; int sum; }; Node tree[4*N]; int a[N]; int fa[N]; void build(int l,int r,int v) { tree[v].l=l; tree[v].r=r; if(l==r) { fa[l]=v; tree[v].sum=a[l]; return ; } int mid=(l+r)>>1; build(l,mid,v*2); build(mid+1,r,v*2+1); tree[v].sum=tree[v+v].sum+tree[v+v+1].sum; } void update(int t,int p) { tree[t].sum+=p; if(t==1) return ; update(t/2,p); } int queue(int a,int b,int v) { if(tree[v].l==a&&tree[v].r==b) { return tree[v].sum; } int mid=(tree[v].l+tree[v].r)>>1; if(b<=mid) return queue(a,b,v+v); else if(a>mid) return queue(a,b,v+v+1); else return queue(a,mid,v*2)+queue(mid+1,b,v*2+1); } int main() { int T,n; char str[10]; int x,y; scanf("%d",&T); for(int cas=1; cas<=T; cas++) { scanf("%d",&n); for(int i=1; i<=n; i++) scanf("%d",&a[i]); build(1,N,1); printf("Case %d:\n",cas); while(scanf("%s",str)>0) { if(str[0]==‘A‘) { scanf("%d %d",&x,&y); update(fa[x],y); } else if(str[0]==‘S‘) { scanf("%d %d",&x,&y); update(fa[x],-y); } else if(str[0]==‘Q‘) { scanf("%d %d",&x,&y); int ans=queue(x,y,1); printf("%d\n",ans); } else { break; } } } }
线段树之单点更新求和hdoj1166
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。