北京大学郭炜教授详解线段树与树状数组的构造与应用

北京大学的信息学院郭炜教授提供了一份内部资料，详细介绍了线段树和树状数组在计算机科学中的应用。线段树，又称为区间树，是一种数据结构，它将线性区间问题转化为树形结构，便于高效处理区间查询、更新等操作。 线段树的特点如下： 1. 概念理解：线段树本质上是一种二叉树，每个节点代表一个区间，区间起点和终点通常为整数。相邻层次的节点区间互不重叠，叶子节点表示的是一些基本的、不可再分的单位区间。 2. 节点划分：非叶节点的子区间通过中点划分，即左儿子表示区间[a, (a+b)/2]，右儿子表示区间[(a+b)/2+1, b]，其中除法结果向下取整。 3. 深度计算：根节点的深度可以通过公式 log2(b-a+1)+1（向上取整）计算，反映节点间的层次关系。 4. 节点数量：叶子节点的数量与根节点表示的区间长度相等，而整个线段树的节点总数为2N-1，其中N为叶子节点数，这是因为线段树是满二叉树，除了根节点外，其余节点都是两个子节点。 5. 区间分解：例如，对于区间[1,9]，分解区间[2,8]时，会找到那些区间完全包含在这个待分解区间内的节点，这些节点作为"终止"节点，它们代表的区间合并起来覆盖了整个目标区间，确保了分解的正确性和效率。 线段树常用于解决区间查询问题，如求区间和、区间最大值、区间最小值等问题，由于其高效的搜索和更新性能，被广泛应用于各种算法和数据结构设计中。郭炜教授提供的课程网页（http://acm.pku.edu.cn/JudgeOnline/summerschool/pku_acm_train.htm）可能包含更深入的讲解和示例，对学习者理解和掌握线段树非常有帮助。上机地点位于理科1号楼1235室，提供了实践操作的机会。