代码 & 建树

建树

思路

• 首先，我们得先明白几件事情:

• 每个结点存什么

• 结点下标是什么

• 如何建树

以一个简单的求一段区间的最大值来描述上面的三个概念

• 对于a[1~6] = {1,8,6,4,3,5}来说，线段树如上所示，红色代表每个结点存储的区间，蓝色代表该区间最值。

• 可以发现，每个叶子结点的值就是数组的值，每个非叶子结点的度都为二，且左右两个孩子分别存储父亲一半的区间。每个父亲的存储的值也就是两个孩子存储的值的最大值。

• 那么结点到底是如何存储区间的呢，以及如何快速找到非叶子结点的孩子以及非根节点的父亲呢，这里也就是理解线段树的重点以及难点所在，线段树你只要理解了结点与结点之间的关系便能很快理解线段树的基本知识。

• 对于一个区间[l,r]来说，最重要的数据当然就是区间的左右端点l和r，但是大部分的情况我们并不会去存储这两个数值，而是通过递归的传参方式进行传递。这种方式可以直接用数组存树，那这里怎么快速使用下标找到左右子树呢?

线段树的基本结构

• 线段树中的每个节点都代表一个区间（可以理解为线段），每个节点维护的是父亲的区间二等分后的其中一个子区间

• 线段树具有唯一的根节点，根节点维护的是整个区间，代表的区间是整个统计范围，比如有序列a[1]~a[N]，那么根节点所代表的区间就是[1,N]。

• 线段树的每个叶子节点都代表一个长度为1的元区间[x,x]

• 对于 每个内部节点[l,r]，它的左子节点是[l,mid]，右子节点是[mid+1,r]，其中mid=(l+r)/2向下取整

• 当有n个元素时，对区间的操作可以在O ( l o g n ) O(logn)O(logn)的时间内完成，空间复杂度为O ( n ) O(n)O(n)。

线段树的基本用途

• 维护区间信息
• 合并区间信息
• 对序列进行维护，支持查询和修改操作