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