link:http://acm.hdu.edu.cn/showproblem.php?pid=1166

今天初学线段树,看了几个讲义,找了道最基础的入门题做了一下,算是一边看讲义一边写代码啊,不过对它的建立,插入,查找过程有了初步的了解,题目中文,很好理解。做的过程中,一个问题老是困扰,就是在询问区间的时候,有一步是query(l,mid)&query(mid+1,r),我自己编的时候,按我的思想写成了query(l,mid)&query(mid,l),就是求两个区间的合并,可我的连编译都无法进行。。后来问人家说,这是把所有的都看成一个叶子点,最后的总和其实就是每个点的总和,所以后面那个mid+1。。。有点小明白,但还不是很透,再做练习了。。下面是我的代码:

code:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define N 50001
struct segtree
{
int l,r,c;
}tree[N*3];
int a[N];
void build(int l,int r,int k)
{
tree[k].l=l;
tree[k].r=r;
if(l==r)
tree[k].c=a[l];
else
{
int mid=(l+r)/2;
build(l,mid,k*2);
build(mid+1,r,k*2+1);
tree[k].c=tree[2*k].c+tree[2*k+1].c;
}
}
void updata(int x,int k,int l)
{
tree[k].c+=x;
if(tree[k].l==l&&tree[k].r==l)
return;
else
{
int mid=(tree[k].l+tree[k].r)/2;
if(l>mid)
updata(x,2*k+1,l);
else
updata(x,2*k,l);
}
}
int query(int l,int r,int k)
{
if(tree[k].l==l&&tree[k].r==r)
return tree[k].c;
int mid=(tree[k].l+tree[k].r)/2;
if(l>mid)
return query(l,r,k*2+1);
else
{
if(r<=mid)
return query(l,r,k*2);
else
return query(l,mid,k*2)+query(mid+1,r,k*2+1);
}
}
int main()
{
int t,n,cas;
int x,y,i;
char s[10];
scanf(“%d”,&t);
for(cas=1;cas<=t;cas++)
{
printf(“Case %d:\n”,cas);
scanf(“%d”,&n);
for(i=1;i<=n;i++)
scanf(“%d”,&a[i]);
build(1,n,1);
while(scanf(“%s”,s)&&s[0]!=’E’)
{
scanf(“%d%d”,&x,&y);
switch(s[0])
{
case ‘A’:updata(y,1,x);break;
case ‘Q’:printf(“%d\n”,query(x,y,1));break;
case ‘S’:updata(-y,1,x);break;
}
}
}
return 0;
}

发表评论

电子邮件地址不会被公开。

Post Navigation