单选题 适中
#22006

对一个大小为16(下标0-15)的数组构建满线段树,查询区间[3,11]时,最少需要访问多少个树结点(包括路径上的父结点和完全包含在查询区间内的结点)?

对一个大小为16(下标0-15)的数组构建满线段树,查询区间[3,11]时,最少需要访问多少个树结点(包括路径上的父结点和完全包含在查询区间内的结点)?

未登录也能判分,登录后才会记录
答案与解析
正确答案:B
解析

满线段树结构为:  

[0,15]分为[0,7]和[8,15];  

[0,7]分为[0,3]和[4,7];  

[8,15]分为[8,11]和[12,15];  

[0,3]分为[0,1]和[2,3]。  

查询[3,11]时,需访问[0,15]、[0,7]、[8,15]、[0,3]、[4,7]、[8,11]、[2,3]、[3,3],共8个节点。