#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;
}
帮我看一下这段线段树的代码应该怎么用?有问题吗?
- 写回答
- 好问题 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 汇编语言除法溢出问题