首页 > 试题广场 >

线段树编号问题

[编程题]线段树编号问题
  • 热度指数：873 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一段线段树构造代码，按如下方式构造线段树。
定义变量ans，初始ans=0
定义函数build(x,y,z)，意义如下
/////////////////////////
start build
   赋值 ans=x
   判断 若(y=z) 则 end build
   定义变量mid
   赋值 mid=(y+z)/2 {此处除法为下取整}
   运行 build(x*2,y,mid)
   运行 build(x*2+1,mid+1,z)
end build
/////////////////////////
你的任务是，对于T组询问，每个询问给出n，求对于每个n，运行build(1,1,n)后，输出ans。对于每个n，询问相互独立，即ans在上一个询问结束后归零。
输入时T单独给出，每个n会存储在数组a中给出。

示例1

输入

2,[4,5]

输出

[7,9]

说明

当n=4时，构造出的线段树的区间编号及其对应的区间为
1[1,4],2[1,2],3[3,4],4[1,1],5[2,2],6[3,3],7[4,4]
当n=5时，构造出的线段树的区间编号及其对应的区间为
1[1,5],2[1,3],3[4,5],4[1,2],5[3,3],6[4,4],7[5,5],8[1,1],9[2,2]
其中[]外的是编号，[]内表示区间的起始位置和终末位置。
可知，当n=4时编号最大为7，当n=5时编号最大为9

备注:
T<=100000
0<n<=10^8
算法知识视频讲解
开通博客
头像 不会做题的小菜鸡
发表于 2021-09-14 12:54:22
思路 题目分析 题目给出了build函数的规则，从根节点开始，递归地按照树的结构进行向下延伸，延伸出一个节点就进行编号。 编号的规则：当前结点编号i时，左子节点编号为i*2，右子节点编号为i*2+1 左右子树的划分规则是根据给定的区间进行二分向下取整划分，直到区间长度为0（结点中左右下标相同）为 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 摸鱼学大师
发表于 2021-08-05 00:02:10
思路： 题目的主要信息： 按照下列要求,使用build(x,y,z)函数构造线段树：start build 赋值 ans=x 判断 若(y=z) 则 end build 定义变量mid 赋值 mid=(y+z)/2 {此处除法为下取整} 运行 build(x*2,y,mid) 运行 b 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 呆喵挠琴
发表于 2021-09-07 00:20:36
思路： 题目的主要信息： 已知build的询问过程，对于T个n，运行build(1,1,n)后，输出每个n询问过程中最大的ans。 ans在每一次询问结束后都清零。 方法一：递归 根据题目意思，直接构造一个函数模拟build的询问过程。同时设置两个全局变量ans和max_ans，设为全局变量的原 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 认认真真coding
发表于 2021-08-08 15:51:55
题目描述给定一段线段树构造代码，按如下方式构造线段树。定义变量ans，初始ans=0定义函数build(x,y,z)，意义如下/////////////////////////start build 赋值 ans=x 判断 若(y=z) 则 end build 定义变量mid 赋值 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 Praying_cqf
发表于 2020-02-14 18:11:44
在很早之前研究线段树的时候发现，以常规方法构造出的线段树编号可能并不连续。因此便有了这一题。 结论1：手写若干个线段树可以发现，若给线段树分层，设区间[1,n]代表的点为第1层，下面是第2层第3层以此类推，我们可以发现，第i+1层的编号永远大于第i层的编号。证明：首先同层的情况下，左边节点编号小于右 展开全文
去ta的博客 赞 (0) 回复(1) 收起

问题信息

基础数学
难度：
2条回答 4558浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号