线段树不是完全二叉树，是平衡二叉树
堆也是平衡二叉树
堆满二叉树：
h层，一共有2^h-1个节点（大约是2^h）
最后一层（h-1层）有2^(h-1)个节点
最后一层的节点数大致等于前面所有层节点之和
如果区间有n个元素，数组表示需要4n的空间
不考虑添加元素，使用4n的静态空间即可
接口：
public interface Merger<E> {
E merge(E a, E b);
}
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, arr.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) / 2;
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();
}
}
测试：
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);
}
}
查找方法：
// 返回区间[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("Index is illegal."); return query(0, 0, data.length - 1, queryL, queryR);
} // 在以treeIndex为根的线段树中[l...r]的范围里，搜索区间[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); E leftResult = query(leftTreeIndex, l, mid, queryL, mid);
E rightResult = query(rightTreeIndex, mid + 1, r, mid + 1, queryR);
return merger.merge(leftResult, rightResult);
}
public class Main {
public static void main(String[] args){
Integer[] nums={-2,0,3,-5,2,-1};
SegmentTree<Integer> segTree = new SegmentTree<>(nums,
(a, b) -> a + b);
System.out.println(segTree.query(0, 2));
}
}
线段树添加：
public class NumArray {
private SegmentTree<Integer> segmentTree;
public NumArray(int[] nums){
if(nums.length>0){
Integer[] data=new Integer[nums.length];
for(int i=0;i<nums.length;i++)
data[i]=nums[i];
segmentTree =new SegmentTree<>(data, (a,b)->a+b);
}
}
public int sumRange(int i,int j){
if(segmentTree==null)
throw new IllegalArgumentException("Segment Tree is null");
return segmentTree.query(i, j);
}
}
不用线段树添加：
public class NumArray2 {
private int[] sum;//sum[i]存储前i个元素和 sum[0]=0
public NumArray2(int[] nums){
sum=new int[nums.length+1];
sum[0]=0;
for(int i=01;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];
}
}
不用线段树修改：(效率很低)
public class NumArray3 {
private int[] sum;
private int[] data;
public NumArray3(int[] nums){
data=new int[nums.length];
for(int i=0;i<data.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 index,int val){
data[index]=val;
for(int i=index+1;i<sum.length;i++)
sum[i]=sum[i-1]+data[i-1];
}
public int sumRange(int i,int j){
return sum[j+1]-sum[i];
}
}
用线段树更新：
//将index位置的值，更新为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;
int leftTreeIndex=leftChild(treeIndex);
int rightTreeIndex=rightChild(treeIndex);
if(index>=mid+1)
set(rightTreeIndex, mid+1,r,index,e);
else
set(leftTreeIndex, l,mid,index,e);
tree[treeIndex]=merger.merge(tree[leftTreeIndex], tree[rightTreeIndex]);
}
public void update(int index,int val){
if(segmentTree==null)
throw new IllegalArgumentException("Segment Tree is null");
segmentTree.set(index,val);
}