「已注销」 2013-07-29 01:58 采纳率: 0%
浏览 2308

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

#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 2014-08-13 16:05
    关注

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

    评论

报告相同问题?

悬赏问题

  • ¥15 ads仿真结果在圆图上是怎么读数的
  • ¥20 Cotex M3的调试和程序执行方式是什么样的?
  • ¥20 java项目连接sqlserver时报ssl相关错误
  • ¥15 一道python难题3
  • ¥15 用matlab 设计一个不动点迭代法求解非线性方程组的代码
  • ¥15 牛顿斯科特系数表表示
  • ¥15 arduino 步进电机
  • ¥20 程序进入HardFault_Handler
  • ¥15 oracle集群安装出bug
  • ¥15 关于#python#的问题:自动化测试