1.什么是线段树
百度百科解释：
线段树是一种二叉搜索树，与区间树相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。
使用线段树可以快速的查找某一个节点在若干条线段中出现的次数，时间复杂度为O(logN)。而未优化的空间复杂度为2N，实际应用时一般还要开4N的数组以免越界，因此有时需要离散化让空间压缩。
其实，线段树就是一棵平衡的二叉树，可以用数组来存储，把数组分成若干个段，每个节点保存一个段，表示一个区间，父节点保存左右子节点区间和，子节点分别表示父节点的左右半区间，如果父节点保存的区间是[a,b],那么左子节点保存的区间为[a,(a+b)/2],右子节点保存的区间为[(a+b)/2+1,b]。
线段树大多数情况下本身是固定的，所以一般不用考虑向线段树中添加和删除元素，线段树要解决的主要是连续区间的动态查询问题，比如一个电商网站，要统计一段时间区间内的用户流量是多少？此时使用线段树效率比较高。
2.为什么要使用线段树
更新区间中一个元素或者一个区间的值,查询一个区间[i,j]的最大值，最小值，或者区间数字和,使用数组时间复杂度为O(n),使用线段树时间复杂度是O(logn),要比使用数组的效率高很多，所以使用线段树进行统计分析是很高效的。
3.线段树图示
4.线段树的查询
如下图，查询[2,5],首先从根节点[0,7]开始查询，[2,5]一部分落在了根节点的左子节点[0,3]上，另一部分落在了根节点的右子节点[4,5]上
，所以把要查询的[2,5]分成查询[2,3]和查询[4,5],这样在根节点的左子节点上查询[2,3]，在根节点的右子节点上查询[4,5]
接下来进行一次遍历，发现[0,3]的左子节点和要查询的[2,3]没关系，则在[0,3]的右子节点[2,3]上查询，发现[2,3就是要查询的值，停止向下遍历，直接取值 即可。查询[4,5]的过程也一样。
5.代码实现：
Merget.java
/**
* 融合器
* @param <E>
*/
public interface Merger<E> {
E merge(E a,E b); //将两个元素融合成一个
}
SegmentTree.java
/**
* 线段树的实现
* @param <E>
*/
public class SegmentTree<E> {
private E[] tree; //存放线段树节点
private E[] data; //存放线段树中的节点元素值
private Merger<E> merger;
public SegmentTree(E[] arr,Merger<E> merger){
this.merger = merger;
data = (E[]) new Object[arr.length];
for (int i = 0; i < arr.length; i++) {
data[i] = arr[i];
}
tree = (E[]) new Object[4 * arr.length];
buildSegmentTree(0,0,data.length - 1);
}
public int getSize(){
return data.length;
}
public E get(int index){
if(index < 0 || index >= data.length)
throw new IllegalArgumentException("非法索引");
return data[index];
}
//返回给定索引表示的左孩子节点的索引
private int leftChild(int index){
return index * 2 + 1;
}
//返回给定索引表示的右孩子的索引
private int rightChild(int index){
return index * 2 + 2;
}
/**
* 线段树的创建
* @param treeIndex 当前节点索引，从0开始
* @param left 左区间端点
* @param right 右区间端点
*/
private void buildSegmentTree(int treeIndex,int left,int right){
if(left == right){
tree[treeIndex] = data[left];
return;
}
int leftTreeIndex = leftChild(treeIndex);
int rightTreeIndex = rightChild(treeIndex);
//区间中点
int mid = (left + right) / 2;
//创建左右区间节点
buildSegmentTree(leftTreeIndex,left,mid);
buildSegmentTree(rightTreeIndex,mid+1,right);
tree[treeIndex] = merger.merge(tree[leftTreeIndex],tree[rightTreeIndex]);
}
@Override
public String toString() {
StringBuilder res = new StringBuilder();
res.append("[");
for (int i = 0; i < tree.length; i++) {
if(tree[i] != null)
res.append(tree[i]);
else
res.append("null");
if(i != tree.length -1)
res.append(",");
}
res.append("]");
return res.toString();
}
//返回区间[queryL,queryR]的值
public E query(int queryL,int queryR){
if(queryL<0 || queryL>=data.length || queryR<0 || queryR>=data.length || queryL>queryR)
throw new IllegalArgumentException("非法索引");
return query(0,0,data.length-1,queryL,queryR);
}
//在以当前节点treeIndex为根的线段树[left,right]范围里搜索区间[queryL,queryR]的值
private E query(int treeIndex,int left,int right,int queryL,int queryR){
if(queryL == left && queryR == right)
return tree[treeIndex];
int mid = (left + right) / 2;
int leftTreeIndex = leftChild(treeIndex);
int rightTreeIndex = rightChild(treeIndex);
if(queryL >= mid+1)
return query(rightTreeIndex,mid+1,right,queryL,queryR);
else if(queryR <= mid)
return query(leftTreeIndex,left,mid,queryL,queryR);
E leftResult = query(leftTreeIndex,left,mid,queryL,mid);
E rightResult = query(rightTreeIndex,mid+1,right,mid+1,queryR);
return merger.merge(leftResult,rightResult);
}
//将index位置的值更新为e
public void set(int index,E e){
if(index < 0 || index > data.length)
throw new IllegalArgumentException("非法索引");
data[index] = e;
set(0,0,data.length-1,index,e);
}
//在以treeIndex为根的线段树中更新index的值为e
private void set(int treeIndex,int left,int right,int index,E e){
if(left == right){
tree[treeIndex] = data[left];
return;
}
int leftTreeIndex = leftChild(treeIndex);
int rightTreeIndex = rightChild(treeIndex);
int mid = (left + right) / 2;
if(index >= mid + 1)
set(rightTreeIndex,mid+1,right,index,e);
else
set(leftTreeIndex,left,mid,index,e);
tree[treeIndex] = merger.merge(tree[leftTreeIndex],tree[rightTreeIndex]);
}
public static void main(String[] args) {
Integer[] nums = {-2,0,3,-5,2,1};
SegmentTree<Integer> segmentTree = new SegmentTree<>(nums,(a,b) ->a + b);
System.out.println(segmentTree);
System.out.println(segmentTree.query(0,3));
}
}
6.线段树应用
LeetCode第303题：区域和检索-数组不可变
给定一个整数数组 nums，求出数组从索引 i 到 j (i ≤ j) 范围内元素的总和，包含 i, j 两点。
示例：
给定 nums = [-2, 0, 3, -5, 2, -1]，求和函数为 sumRange()
sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3
说明:
- 你可以假设数组不可变。
- 会多次调用 sumRange 方法。
1.使用线段树： 如图代码,将我们自己写的融合器接口和线段树的类复制到LeetCode，作为内部类。
2.不使用线段树：
class NumArray {
private int[] sum;//sum[i]存储前i个元素的和，sum[0] = 0
//sum[i]存储的nums[0...i-1]的和
public NumArray(int[] nums) {
sum = new int [nums.length + 1];
sum[0] = 0;
for (int i = 1; i < sum.length; i++) {
sum[i] = sum[i-1] + nums[i-1];
}
}
public int sumRange(int i, int j) {
return sum[j+1] - sum[i];
}
}
LeetCode第307题：区域和检索-数组可修改
给定一个整数数组 nums，求出数组从索引 i 到 j (i ≤ j) 范围内元素的总和，包含 i, j 两点。
update(i, val) 函数可以通过将下标为 i 的数值更新为 val，从而对数列进行修改。
示例:
Given nums = [1, 3, 5]
sumRange(0, 2) -> 9
update(1, 2)
sumRange(0, 2) -> 8
说明:
- 数组仅可以在 update 函数下进行修改。
- 你可以假设 update 函数与 sumRange 函数的调用次数是均匀分布的
1.不使用线段树（性能很差，提交时可能会报超出时间限制）
class NumArray {
private int[] sum; //sum[i]存储前i个元素的和，sum[0] = 0
//sum[i]存储的nums[0...i-1]的和
private int[] data;
public NumArray(int[] nums){
data= new int[nums.length];
for (int i = 0; i < nums.length; i++) {
data[i] = nums[i];
}
sum = new int [nums.length + 1];
sum[0] = 0;
for (int i = 1; i < sum.length; i++) {
sum[i] = sum[i-1] + nums[i-1];
}
}
public void update(int i,int val){
data[i] = val;
for(int j = i+1;j<sum.length;j++){
sum[j] = sum[j-1] + data[j-1];
}
}
public int sumRange(int i,int j){
return sum[j+1] - sum[i];
}
}
每一次的updata操作都是O(n)的时间复杂度，如果该操作进行m次，则整体的时间复杂度就是O(m*n)，所以执行的速度是很慢的。
2.使用线段树
每一次sumRange和update操作的时间复杂度都为O(logn),各调用m次，各自总的时间负责度均为O(m*logn),比不使用线段树性能提升很多。
7.总结：
这篇介绍了线段树的概述，查询，以及代码实现，最后借LeetCode上两道区域检索的问题进行线段树的应用。分别都用了两种方法：使用线段树和使用数组，唯一不同的是第二个问题的数组是可以更新的，需要动态更新某个区间内的数组值，这样一比较使用线段树的优势就凸显出来了，我们已经知道，使用数组查询和更新的时间复杂度都是O(n),而使用线段树进行查询和更新的操作的时间复杂度都为O(logn),在上面第二个问题的中使用线段树的性能优势体现的非常明显。所以当需要动态更新区间值的时候，使用线段树是一个不错的选择。
