数据结构-线段树

线段树定义：

    线段树是一种二叉搜索树，又叫区间树，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点，根节点存储的是左右孩子节点范围的和。

线段树的定义

    线段树不是完全二叉树，因为元素不是从左往右放的。但是线段树却是平衡二叉树（在一个树上，对于任意一个节点，左子树和右子树的高度差不能超过1）。

线段树的使用场景：

对于给定的区间：

更新：更新区间中的一个元素或者一个区间的值。

查询一个区间[i,j]的最大值，最小值，或者区间数字和。

线段树使用场景

使用数组来表示线段树：

    可以将线段树看成满二叉树，然后用数组来表示这个线段树，最后一层多余的元素使用null来表示。

    对于元素个数为 n 的数组，使用高度为 h 的满线段树来表示时，最后一层的节点数为 n，即在满线段树的下标和原数组是一致的，于是 n = 2^(h - 1)；同时，对于满线段树来说，除了最后一层，其上面的所有层节点之和，有 2^(h - 1) - 1个节点。

    总结：对于满线段树，最后一层的节点数大致等于前面所有层节点之和，并且等于原数组元素个数。

数组表示线段树

于是，对于满二叉树（n = 2^k）只需要 2n 的空间；对于非满二叉树（n = 2^k + 1），会比满二叉树多了一层，也就是多了 2n 的空间，故需要 4n 空间。

数组表示线段树

线段树的结构：

成员变量：

E[] data，元素数组；

E[] tree，表示使用数组存放线段树；

Merger merger，合并策略，根据不同业务选择不同策略。

线段树变量 合并策略接口 根据根节点下标获取左右孩子下标

将数组转换为线段树：

    思路：在线段树SegmentTree 构造器中，将传进来的数组进行转换。首先为线段树数组开辟数组元素的4倍空间，然后递归执行在 treeIndex 的位置创建表示区间[l,r]的线段树。递归终止条件是走到最后一层，即 l== r，将父亲节点的区间拆分为左右孩子区间，区间的分界线为 mid = l + (r - l)/2，然后让左右孩子执行递归操作，每一步递归操作，都要为当前 treeIndex 位置线段树赋值，即将其左右孩子的范围合并。

数组转线段树

在线段树中查询某个区间：

    思路：先在根节点区间[l,r]查找该区间[queryL,queryR]，首先对根节点进行拆分，区间分界线为  mid = l + (r - l)/2，如果查询区间的右边界小于等于 mid，即 queryR <= mid，说明查询的区间[queryL, queryR]在左子树区间[l,mid]范围内，此时直接到左子树递归查询即可；如果查询区间的左边界大于 mid，即 queryL > mid，说明查询的区间[queryL, queryR]在右子树区间[mid + 1,r]范围内，此时直接到右子树递归查询即可；如果queryL <= mid < queryR，表示查询的区间[queryL, queryR]在散落在左右子树上，此时需要将[queryL, queryR]区间拆分为[queryL,mid]和[mid + 1,queryR]分别在左右子树上递归查询，最后需要为 treeIndex位置的根节点赋值，即合并左右子树查询的结果。

查询某个区间

更新数组下标为index的值：

    思路:首先更新数组下标index的值，data[index] = e，让，然后递归更新线段树数组。从根节点开始更新，首先对根节点进行拆分，区间分界线为 mid = l + (r - l)/2，如果 index > mid，说明要更新的元素在右子树，此时递归更新右子树[mid + 1,r]下的下标为index元素就行了；反之，说明要更新的元素在左子树，此时递归更新左子树[l,mid]下的下标为index的元素即可。最后，需要更新 treeIndex位置的根节点的值，即合并左右子树更新的结果。

线段树的更新