「已注销」 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 求差集那个函数有问题,有无佬可以解决
  • ¥15 【提问】基于Invest的水源涵养
  • ¥20 微信网友居然可以通过vx号找到我绑的手机号
  • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
  • ¥15 解riccati方程组
  • ¥15 display:none;样式在嵌套结构中的已设置了display样式的元素上不起作用?
  • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
  • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
  • ¥50 树莓派安卓APK系统签名
  • ¥65 汇编语言除法溢出问题