线段树
- 每个节点表示一个区间内相应的信息。
- 叶子节点只存一个元素(区间为1)。
- 线段树不是完全二叉树，也不是满二叉树。
- 线段树是平衡二叉树(最大深度与最小深度差距不会超过1，堆也是平衡二叉树，logn)。
- 一般不考虑向线段树中添加和删除元素，且固定区间。
- 可将其看做一个节点可以为空的满二叉树(特殊的完全二叉树)，可用数组表示。
- 用数组表示线段树应开辟4倍空间。
对于满二叉树：有(2^h - 1) 个节点，大约2^h。 最后一层(叶子节点)的节点数是2^(h-1) 约等于前面所有层节点之和。
所以如果线段树是区间有n个元素(叶子节点为n)，当n = 2^h，只需要开辟2n的空间足以存全部节点。如果n= 2^k + 1, 最后一层只有少数几个叶子节点，则需要开辟4n的空间节点(将其视其余叶子节点为空的满二叉树)。
满二叉树
线段树
节点视为空
代码示例 创建线段树
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[arr.length * 4];
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("Index is illegal");
return data[index];
}
private int leftChild(int index){
return 2*index + 1;
}
private int rightChild(int index){
return 2*index + 2;
}
// 在treeIndex的位置创建区间为[l...r]的线段树
private void buildSegmentTree(int treeIndex, int l, int r){
if (l == r){
tree[treeIndex] = data[l];
return;
}
int mid = l + (r - l) /2;
int leftTreeIndex = leftChild(treeIndex);
int rightTreeIndex = rightChild(treeIndex);
buildSegmentTree(leftTreeIndex, l, mid);
buildSegmentTree(rightTreeIndex, mid + 1, r);
tree[treeIndex] = merger.merge(tree[leftTreeIndex], tree[rightTreeIndex]);
}
}
查询
//返回区间[queryL, queryR]的值
public E query(int queryL, int queryR){
if (queryL >= data.length || queryL < 0 || queryR >= data.length || queryR < 0 || 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;
int leftTreeIndex = leftChild(treeIndex);
int rightTreeIndex = rightChild(treeIndex);
if (queryR <= mid) {
return query(leftTreeIndex, l, mid, queryL, queryR);
} else if (queryL >= mid + 1) {
return query(rightTreeIndex, mid + 1, r, queryL, queryR);
}
E leftResult = query(leftTreeIndex, l, mid, queryL, mid);
E rightResult = query(rightTreeIndex, mid + 1, r, mid + 1, queryR);
return merger.merge(leftResult, rightResult);
}
更新
//更新
public void set(int index, E e){
if (index < 0 || index > data.length)
throw new IllegalArgumentException("Illegal index");
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;
int leftTreeIndex = leftChild(treeIndex);
int rightTreeIndex = rightChild(treeIndex);
if (index <= mid){
set(leftTreeIndex, 0, mid, index, e);
} else {
set(rightTreeIndex, mid + 1, r, index, e);
}
tree[treeIndex] = merger.merge(tree[leftTreeIndex], tree[rightTreeIndex]);
}
时间复杂度
时间复杂度为：O(logn)
相关题目：LeetCode 303 区域与检索
