CSP-S 提高级 · CSP 2025 提高级第一轮 第 3 题

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

这题考线段树查询的节点访问计数。满树16个叶子，查询[3,11]得8个节点。关键是别漏路径上的父节点，只要部分重叠就要继续往下走，完全包含才停止。

很多同学只数完全落在区间里的叶子或子区间节点，比如数了[3,3]、[4,5]、[6,7]、[8,11]这几个完全包含的，觉得够了。其实线段树查询是递归的：只要当前节点区间和查询区间有交集，就必须访问这个节点。如果只重叠一部分，还得继续访问它的孩子。这道题里，根节点[0,15]和左孩子[0,7]、右孩子[8,15]都只重叠一部分，必须访问；[0,7]下的[0,3]也只重叠一部分，要访问；[0,3]下的[2,3]部分重叠，也要访问。漏掉这些‘部分重叠’的父节点，答案就会偏小。

考察知识点

数据结构 — 线段树

概念定义

• 线段树：二叉树结构，每个结点代表一个区间 [l, r]。叶结点对应单个元素，父结点对应子区间的并集。
• 满线段树：叶子数量是 2 的幂的线段树。叶子数 16（2^4），共 4 层。
• 区间查询：递归访问结点时，有三种情况：①完全在查询区间外（跳过）；②完全被包含（直接返回，不深入）；③部分重叠（递归访问左右孩子）。

逐步推导

大小为 16 的满线段树（下标 0~15），查询 [3,11]：

访问结点路径：

• [0,15] 部分重叠 → 访问

- [0,7] 部分重叠 → 访问 - [0,3] 部分重叠 → 访问 - [2,3] 部分重叠 → 访问 [3,3] 完全在内 → 访问 - [4,7] 部分重叠 → [4,5] 完全在内 → 访问；[6,7] 完全在内 → 访问 - [8,15] 部分重叠 → [8,11] 完全在内 → 访问

总共访问 8 个结点（根据标准线段树实现）。

避坑指南

线段树的结点数统计：每个“访问”都计数（包括路径上的分支结点和完全包含的结点）。很多同学容易只数完全包含的结点，漏掉路径上的部分重叠结点。

考频与趋势

本题出自 CSP 提高级 2025 第 3 题。从题库数据看，线段树考点共考过 1 题，覆盖 1 个考试级别（2025-2025）；逐年分布：2025 年 1 题；分赛事：CSP 提高级 1 题。

预测

基于现有数据，线段树在 CSP 提高级中的考频较低，暂无足够依据预测未来具体出题形式或年份。