CSP-S 2025 第一轮 第3题：对一个大小为 16（下标 0\sim 15）的数组上构建满线段树。查询区间 [3

题目

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

选项

• A. $7$
• B. $8$
• C. $9$
• D. $10$

答案

B

题解

选 B，$8$ 个。

线段树查询的原则是：遇到完全包含在查询区间内的结点，就直接使用它，不再向下访问；不相交的子树直接跳过。

查询 $[3,11]$ 时，最少需要访问这些结点：

``text [0,15] ├── [0,7] │ ├── [0,3] │ │ └── [2,3] │ │ └── [3,3] ← 完全包含，停止向下 │ └── [4,7] ← 完全包含，停止向下 └── [8,15] └── [8,11] ← 完全包含，停止向下 ``

其中：

• 完全包含的结点有 3 个：$[3,3]$、$[4,7]$、$[8,11]$。
• 路径上的父结点有 5 个：$[0,15]$、$[0,7]$、$[0,3]$、$[2,3]$、$[8,15]$。

合计 $3+5=\boxed{8}$ 个。