假设需要频繁求数组的区间和，我们可能会想到树状数组，或者是前缀和，但如果是求区间的最大值或者区间最小值呢？很明显使用树状数组或者前缀和是无能为力了，但我们可以使用另外一种数据结构-线段树。
线段树是一棵平衡的二叉搜索树，它将每个长度大于 1 的区间划分为左右两个区间递归求解。如果整个区间的长度为 n ，则线段树有 n 个叶子节点，每个叶子节点代表一个单位区间，每个内部节点可以直接获取区间的值（最大值，最小值，区间和等）。线段树是建立在线段的基础上，每个节点都代表了一条线段 [a,b] ，在叶子节点中 a==b ，对于非叶子节点它的左子节点区间为 [a,(a+b)/2] ，右子节点区间为 [(a+b)/2+1,b] 。在前面 1.1.4 中我们讲树状数组的时候，提到树状数组可以进行区间的修改及查询，但树状数组主要用于区间的求和，功能比较单一，而线段树不光能用于区间的求和，还能用于区间求最大值，最小值，最大公约数等。
能用于线段树的两个子节点的结果必须能合并，比如求和以及求最大值等，区间和=左子节点和+右子节点和，区间最大值= max(左子节点的最大值，右子节点的最大值)。如果不能合并是没法使用线段树的，比如求众数，左子节点的众数和右子节点的众数可能不是一个，没法合并。这里用求“区间和”为例来介绍线段树，求区间的最大值和最小值原理基本上都一样，这里不在介绍。假设有一个长度为 10 的数组 [1,2,3,4,5,6,7,8,9,10] ，通过他来构建线段树，如下图所示。
我们看到叶子节点都存储的是原数组中的值，非叶子节点存储的是区间的和。在线段树中如果父节点的下标是 i ，他的左右两个子节点的下标分别为 i*2+1 和 i*2+2 。线段树中有两个数组，一个是原数组，一个是线段树数组。
int[] nums;// 原数组。
int[] trees;// 线段树数组，长度是原数组长度的4倍。
构建线段树
线段树是一棵平衡的二叉搜索树，构建的时候可以使用递归的方式构建。
// 调用方式 build(0, 0, nums.length - 1);
// 调用之前要先初始化nums和trees数组。
void build(int root, int left, int right) {
if (left == right) {// 到叶子节点，直接对线段树数组赋值。
trees[root] = nums[left];
} else {
// 递归构建左子树和右子树。
int mid = (left + right) >>> 1;
build(root * 2 + 1, left, mid);
build(root * 2 + 2, mid + 1, right);
// 类似于二叉树的后续遍历，子节点计算完之后在计算当前节点。
pushUp(root);
}
}
// 往上推。
void pushUp(int i) {
// 求区间和，父节点的值等于左右子节点之和。
trees[i] = trees[i * 2 + 1] + trees[i * 2 + 2];
// 如果是求区间最大值可以这样写。
// trees[i] = Math.max(trees[i * 2 + 1], trees[i * 2 + 2]);
}
单点查询
单点查询是从线段树的根节点开始往下查询，直到叶子节点，最后叶子节点的值就是我们要查找的结果。
// 单点查询。
int querySingle(int pos) {
if (pos < 0 || pos >= nums.length)
return -1;
return querySingleHelper(0, 0, nums.length - 1, pos);
}
/**
* @param root 当前节点
* @param start 当前节点的左区间
* @param end 当前节点的右区间
* @param pos 要查询的值
* @return
*/
int querySingleHelper(int root, int start, int end, int pos) {
if (start == end)// 到叶子节点直接返回。
return trees[root];
int mid = (start + end) >>> 1;
if (pos <= mid)// 在左子节点查找。
return querySingleHelper(root * 2 + 1, start, mid, pos);
// 在右子节点查找。
return querySingleHelper(root * 2 + 2, mid + 1, end, pos);
}
单点修改
单点修改和单点查询类似，他是先找到叶子节点，最后在进行修改，修改完之后父节点值也会发生变动，所以还需要往上推，更改父节点的值，一直到根节点，如下图所示。
我们看到子节点的值改了，父节点的值都要跟着改变。
// 单点更新，nums[pos]+=val
void updateSingle(int pos, int val) {
if (pos < 0 || pos >= nums.length)
return;
updateSingleHelper(0, 0, nums.length - 1, pos, val);
}
void updateSingleHelper(int root, int start, int end, int pos, int val) {
if (start == end) {// 已经到叶子节点了，直接更新。
trees[root] += val;// 这里是相对值，是加，不是直接赋值。
} else {
int mid = (start + end) >>> 1;
if (pos <= mid)// 目标位置在左边。
updateSingleHelper(root * 2 + 1, start, mid, pos, val);
else// 目标位置在右边。
updateSingleHelper(root * 2 + 2, mid + 1, end, pos, val);
pushUp(root);// 往上推，更新父节点的值。
}
}
区间查询
区间查询会有下面 4 种情况。如果查找区间非常大，包含了节点区间，直接返回当前节点值即可。如果查找区间只在左子树，就在左子树查找，如果只在右子树，就在右子树查找，否则左右两个子树都要查，如下图所示。
假设查找 [2,5] 之间的和，查找步骤如下图所示。
// 区间查询。
int queryRange(int left, int right) {
return queryRangeHelper(0, 0, nums.length - 1, left, right);
}
int queryRangeHelper(int root, int start, int end, int left, int right) {
// 当前节点在查找的区间之内，直接返回该节点的值。
if (left <= start && right >= end)
return trees[root];
int mid = (start + end) >>> 1;
int sum = 0;
if (left <= mid)// 在左边查找。
sum += queryRangeHelper(root * 2 + 1, start, mid, left, right);
if (right > mid)// 在右边查找，注意这里没有else，因为查找区间可能两边都有。
sum += queryRangeHelper(root * 2 + 2, mid + 1, end, left, right);
return sum;
}
区间修改
区间修改可以参考单点修改，一直往下找到叶子节点，把它的值给修改，然后还要一直往上修改父节点值。区间修改不同于单点修改的地方在于区间修改可能两个子节点都要修改，就像区间查询一样。
// 区间修改，把区间[left,right]中所有的数字加上val。
void updateRange(int left, int right, int val) {
updateRangeHelper(0, 0, nums.length - 1, left, right, val);
}
void updateRangeHelper(int root, int start, int end, int left,
int right, int val) {
if (start == end) {
trees[root] += val;// 到叶子节点，值加上val。
} else {
int mid = (start + end) / 2;
if (left <= mid)// 在左子节点修改。
updateRangeHelper(root * 2 + 1, start, mid, left, right, val);
if (right > mid)// 在右子节点修改，和查询一样，也是没有 else。
updateRangeHelper(root * 2 + 2, mid + 1, end, left, right, val);
pushUp(root);// 往上推，更新父节点的值。
}
}
懒标记
我们看到区间修改的时候他会把每一个叶子节点都要修改，然后在往上更新父节点，实际上可以不这样做，如果某个子树的值全部要修改，只需要更改这棵子树的根节点即可，给他加个标记，然后这棵子树的子节点都不要修改了。就像过年别人给你压岁钱一样，这个钱不是直接给你，而是先给你妈，然后你妈在给你们。由于给的人太多（类似于区间的频繁修改），你妈说这个钱就不一一发给你们了，放我这保管，需要的时候在给你们。
假设我们需要给区间 [3,9] 中的所有节点都加上 10 ，当我们找到需要更新的节点区间 [3,4] 和 [5,9] 的时候，只需要修改他们的值就可以了，然后给他加个懒标记值，他们的子节点就不在修改了，但他们的父节点还是要更新，如下图所示。
假如需要查询区间 [3,7] ，首先他会在 [0,4] 和 [5,9] 两个子节点中查找，节点 [0,4] 又会在节点 [3,4] 查找，而 [3,7] 区间包含 [3,4] 区间，可以直接返回区间 [3,4] 的值。而 [3,7] 区间不全部包含 [5,9] 区间，所以会到节点 [5,9] 的子节点去找，因为节点 [5,9] 有懒标记，所以在到子节点查找之前，懒标记必须下发到子节点，所以代码中多了一个懒标记数组 lazy 。
int[] nums;// 原数组。
int[] trees;// 线段树数组。
int[] lazy;// 懒标记数组。
。。。。。。
剩余部分参考：《博哥的算法秘籍》第 1 章数据结构。
| 数组，滚动数组，差分数组，树状数组 | |
| 链单向表，双向链表，循环链表，跳表，异或链表 | |
| 队列，循环队列，双端队列 | |
| 栈 | |
| 散列表 | |
| 二叉树，二叉搜索树，AVL树，红黑树，字典树，哈夫曼树，线段树，笛卡尔树 | |
| 堆 | |
| 图的介绍，图的遍历，Dijkstra算法，Bellman-Ford算法，SPFA算法，Floyd算法，Prim算法，Kruskal算法，Boruvka算法，拓扑排序 |
