线段树篇(1)—— 创建线段树
1 线段树(区间树)(Segment Tree)
- 线段树不是完全二叉树
- 线段树是平衡二叉树;
-
平衡二叉树:最大深度和最小深度只差最多为1;
1.1 为何使用线段树
对于有些问题,关注的是线段(区间)
1.2 操作
- 更新: 更新区间中一个元素或者一个区间的值;
- 查询一个区间【i,j】的最大值,最小值或者区间数字和;
1.3 如果区间有 n 个元素,数组表示需要有多少节点?
0层 - 1
1层 - 2
3层 - 4
3层 - 8
....
h-1 层 - 2 ^ (h-1)
- 对于满二叉树:h 层,一共有 2^h -1 个节点(大约 2 ^h);
- 最后一层(h-1 层),有 2^(h-1) 个节点;
- 最后一层的节点数大致等于前面所有曾节点之和;
- 如果 n = 2^k, 只需要 2n 空间
- 最坏情况,如果 n = 2^k +1, 需要 4n 空间
2 创建线段树
Merger.java
package tree;
public interface Merger<E> {
E merge(E a, E b);
}
SegmentTree.java
package tree;
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);
}
// 在treeIndex 的位置创建表示区间 [l,r] 的线段树
private void buildSegmentTree(int treeIndex, int l, int r) {
if (l == r) {
tree[treeIndex] = data[l];
return;
}
int leftTreeIndex = leftChild(treeIndex);
int rightTreeIndex = rightChild(treeIndex);
int mid = l + (r - l) / 2;
buildSegmentTree(leftTreeIndex, l, mid);
buildSegmentTree(rightTreeIndex, mid + 1, r);
tree[treeIndex] = merger.merge(tree[leftTreeIndex], tree[rightTreeIndex]);
}
public int getSize() {
return data.length;
}
public E get(int index) {
if (index < 0 || index >= data.length) {
throw new IllegalArgumentException("index is illegal");
}
return data[index];
}
// 返回完全二叉树的数组表示中,一个索引所表示的元素的左孩子
private int leftChild(int index) {
return 2 * index + 1;
}
private int rightChild(int index) {
return 2 * index + 2;
}
@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();
}
}
Main.java
package tree;
public class Main {
public static void main(String[] args) {
Integer[] nums = {-2, 0, 3, -5, 2, -1};
// SegmentTree<Integer> segTree = new SegmentTree<>(nums, new Merger<Integer>() {
// @Override
// public Integer merge(Integer a, Integer b) {
// return a + b;
// }
// });
SegmentTree<Integer> segTree = new SegmentTree<>(nums, (a, b) -> a + b);
System.out.println(segTree);
}
}
[-3, 1, -4, -2, 3, -3, -1, -2, 0, null, null, -5, 2, null, null, null, null, null, null, null, null, null, null, null]
Process finished with exit code 0