2 u011537359 u011537359 于 2013.07.29 09:58 提问

帮我看一下这段线段树的代码应该怎么用?有问题吗?

#include
#define MAXN 10005
struct node
{
int left;
int right;
int mid;
int cover;
};
node SegTree[3*MAXN];
void BuildSegTree(int l,int r,int num)
{
SegTree[num].left=l;
SegTree[num].right=r;
SegTree[num].mid=(l+r)/2;
if(l+1!=r)
{
BuildSegTree(l,SegTree[num].mid,2*num);
BuildSegTree(SegTree[num].mid,r,2*num+1);
}
}
void InsertSegTree(int l,int r,int num)
{
if(SegTree[num].left==l&&SegTree[num].right==r)
{
SegTree[num].cover=1;
return;
}
if(r<=SegTree[num].mid)
{
InsertSegTree(l,r,2*num);
}
else if(l>=SegTree[num].mid)
{
InsertSegTree(l,r,2*num+1);
}
else
{
InsertSegTree(l,SegTree[num].mid,2*num);
InsertSegTree(SegTree[num].mid,r,2*num+1);
}
}
int CalSegTree(int num)
{
if(SegTree[num].cover)
{
return SegTree[num].right-SegTree[num].left;
}
if(SegTree[num].left+1==SegTree[num].right)
{
return 0;
}
return CalSegTree(2*num)+CalSegTree(2*num+1);
}
int main()
{
int n,i;
scanf("%d",&n);
BuildSegTree(1,n,1);
int x,y;
for(i=1;i<=n;i++)
{
scanf("%d%d",&x,&y);
InsertSegTree(x,y,1);
}
printf("\n");
while(1)
{
scanf("%d",&x);
printf("%d\n\n",CalSegTree(x));
}
return 0;
}

1个回答

zhb1997
zhb1997   2014.08.14 00:05

什么叫怎么用啊……
线段树是一种数据结构,支持在log2n的时间复杂度下区间修改、询问
不过看了下你的代码,只支持区间加上一个值

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!