线段树（SegmentTree）
线段树（segment tree）顾名思义， 是用来存放给定区间（segment or interval）内对应信息的一种数据结构。
使用线段树可以解决如下问题：
- 维护区间信息；
- 合并区间信息；
- 对序列进行维护，支持查询与修改操作；
一、线段树思想
线段树可以看作是一棵平衡二叉树。母结点代表整个区间的和，越往下区间越小。注意，线段树的每个节点都对应一条线段（区间），但并不保证所有的线段（区间）都是线段树的节点，这两者应当区分开。
如果有一个数组[1,2,3,4,5]，那么它对应的线段树大概长这个样子：
二、线段树建树
在建立线段树时，建树方式如下：
从根节点即存储 [ 0 , length-1 ] 的情况时开始建立；
递归二分每个区间，将 [ l , r ] 区间分解为 [ l , mid ] 和 [ mid + 1 , r ] 两个区间，其中设
；
当递归结束时，分解到的叶结点 [ i , i ] 存储对应的节点值；
递归回溯时，从下往上更新信息，即 val [l, r] = val
+ val
的和；
/**
* 构建线段树
*
* @param treeIndex 创建线段树根节点对应的索引
* @param l 左边界
* @param r 右边界
*
* <p>
* 每个节点 treeIndex 的左右子节点的编号分别为 [treeIndex * 2] 和 [treeIndex * 2+ 1]
* </p>
*/
private void buildSegmentTree(int treeIndex, int l, int r) {
if (l == r) // 递归到叶子节点
tree[treeIndex] = data[l]; // 用数组中的数据赋值
else {
int midIndex = l + (r - l) / 2;
int leftChildIndex = leftChild(treeIndex);
int rightChildIndex = rightChild(treeIndex);
buildSegmentTree(leftChildIndex, l, midIndex);
buildSegmentTree(rightChildIndex, midIndex + 1, r);
tree[treeIndex] = iMerger.merge(tree[leftChildIndex], tree[rightChildIndex]);
}
}
三、单节点修改
若要将 index 位置的值更新为 e ，过程如下:
- 从根节点代表的区间 [ 0 , length-1 ] 出发，递归找到存储区间 [ index , index ] 的叶节点 data[ index ] = e ；
- 再从下往上更新存储区间 [ index , index ] 其根节点路径上的所有区间信息；
/**
* 将index位置的值，更新为e
*
* @param index 更新索引的位置
* @param e 更新后的元素e
*/
public void set(int index, E e) {
if (index < 0 || index >= data.length)
throw new IllegalArgumentException("Index is illegal");
data[index] = e;
set(0, 0, data.length - 1, index, e);
}
// 在以treeIndex为根的线段树中更新index的值为e
private void set(int treeIndex, int l, int r, int index, E e) {
if (l == r) {
tree[treeIndex] = e;
return;
}
int mid = l + (r - l) / 2;
// treeIndex的节点分为[l...mid]和[mid+1...r]两部分
int leftTreeIndex = leftChild(treeIndex);
int rightTreeIndex = rightChild(treeIndex);
if (index >= mid + 1)
set(rightTreeIndex, mid + 1, r, index, e);
else // index <= mid
set(leftTreeIndex, l, mid, index, e);
tree[treeIndex] = iMerger.merge(tree[leftTreeIndex], tree[rightTreeIndex]);
}四、区间查询
要查询在区间 [ l , r ] 上的区间信息，则从根节点开始，递归时会遇到三种情况：
- 要查询的区间 [ l , r ] 属于左孩子部分；
- 要查询的区间 [ l , r ] 属于右孩子部分；
- 要查询的区间 [ l , r ] 部分归属于左孩子，部分归属于右孩子；
/**
* 在以treeIndex为根的线段树中[l...r]的范围里，搜索区间[queryL...queryR]的值
*
* @param queryL 查询左边界
* @param queryR 查询右边界
* @return 区间信息
*/
public E query(int queryL, int queryR) {
if (queryL < 0 || queryL >= data.length ||
queryR < 0 || queryR >= data.length || queryL > queryR)
throw new IllegalArgumentException("Index is illegal.");
return query(0, 0, data.length - 1, queryL, queryR);
}
private E query(int treeIndex, int l, int r, int queryL, int queryR) {
if (l == queryL && r == queryR)
return tree[treeIndex];
int mid = l + (r - l) / 2;
// treeIndex的节点分为[l...mid]和[mid+1...r]两部分
int leftTreeIndex = leftChild(treeIndex);
int rightTreeIndex = rightChild(treeIndex);
if (queryL >= mid + 1)
return query(rightTreeIndex, mid + 1, r, queryL, queryR);
else if (queryR <= mid)
return query(leftTreeIndex, l, mid, queryL, queryR);
// 横跨左右,将查询切分为 [searchL,midIndex] 和 [midIndex+1,searchR] 然后再合并
E leftResult = query(leftTreeIndex, l, mid, queryL, mid);
E rightResult = query(rightTreeIndex, mid + 1, r, mid + 1, queryR);
return iMerger.merge(leftResult, rightResult);
}
五、完整代码示例
https://github.com/perkinls/java-summary/
关注公众号 ，专注于java大数据领域离线、实时技术干货定期分享！如有问题随时沟通交流！ www.lllpan.top
正文到此结束
