线段树（segment tree）是一种基于分治思想的二叉树，它的每个节点都对应一个[ L , R ]区间，叶子节点对应的区间 L = R 。每一个非叶子节点[ L , R ]其左子节点的区间都为[ L , ( L + R )/2]，右子节点的区间都为[( L + R )/2+1, R ]。[1, 10]区间的线段树如下图所示。

因为线段树对区间进行二分，是一棵平衡二叉树，所以树高为 O (log n )，树上的操作大多与树高相关。线段树主要用于更新和查询，一般至少有一个是区间更新或查询。更新和查询的种类变化多样，灵活运用线段树可以解决多种问题。

1. 线段树的存储方式

对于区间最值（最大值或最小值）查询问题，线段树的每个节点都包含三个域： l、r、 mx，其中 l 和 r 分别表示区间的左右端点，mx表示[ l , r ]区间的最值。本题以最大值为例，若有10个元素 a [1..10]={5, 3, 7, 2, 12, 1, 6, 4, 8, 15}，则构建的线段树如下图所示。

线段树除了最后一层，其他层构成一颗满二叉树，因此采用顺序存储方式，用一个数组tree[]存储节点。若一个节点的存储下标为 k ，则其左子节点的下标为2 k ，其右子节点的下标为2 k +1。

线段树根节点的存储下标为1，其左右子节点的存储下标分别为2、3，有10个元素的线段树，其存储下标如下图所示。

2. 创建线段树

可以采用递归的方法创建线段树，算法步骤如下。

（1）若是叶子节点（ l = r ），则节点的最值就是对应位置的元素值。

（2）若是非叶子节点，则递归创建左子树和右子树。

（3）节点的区间最值等于该节点左右子树最值的最大值。

算法代码：

3. 点更新

点更新指修改一个元素的值，例如将 a [ i ]修改为 v 。采用递归进行点更新，算法步骤如下。

（1）若是叶子节点，满足 l = r 且 l = i ，则修改该节点的最值为 v 。

（2）若是非叶子节点，则判断是在左子树中更新还是在右子树中更新。

（3）返回时更新节点的最值。

例如，修改第5个节点的值为14时，先从树根向下找第5个元素所在的叶子节点，将其最值修改为14，返回时更新路径上所有节点的最值（左右子节点最值的最大值）。

算法代码：

4. 区间查询

区间查询指查询一个[ l , r ]区间的最值。采用递归的方法进行区间查询的算法步骤如下。

（1）若节点所在的区间被查询区间[ l , r ]覆盖，则返回该节点的最值。

（2）判断是在左子树中查询，还是在右子树中查询。

（3）返回最值。

例如，在[1, 10]的线段树中查询[3, 5]区间的最值，过程如下。

（1）计算树根[1, 10]的划分点，mid=(1+10)/2=5，待查询区间 l =3、 r =5、 r ≤mid，说明查询区间在左子树中，到左子树中查询。

（2）计算左子树树根[1, 5]的划分点，mid=(1+5)/2=3，待查询区间 l =3、 r =5、 r >mid、 l ≤mid，说明查询区间横跨左右子树两个区间，需要到左、右子树中查询[3, 5]，然后求最大值。

（3）计算左子树树根[1, 3]的划分点，mid=(1+3)/2=2，待查询区间 l =3、 r =5、 l >mid，说明查询区间在右子树中，到右子树中查询，该右子树[3, 3]被查询区间覆盖，返回最值7。

（4）右子树为[4, 5]，待查询区间为[3, 5]，被查询区间覆盖，返回区间最值12。

（5）左右子树分别返回最值7、12，然后求最大值，即可得到查询区间[3, 5]的最值为12。

算法代码： 56QlSRUQ+jV76aFDhi/kJfnOBopUFeDJMWXCANOw0hO4VWHU7X7aA+hXi1PxeDaD