文章目录提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档
- 线段树代码
线段树代码
public class SegmentTree{ //线段树 private E[] tree; //数据 private E[] data; //融合器 private Merger merger; public SegmentTree(E[] arr) { data = (E[])new Object [arr.length]; tree = (E[])new Object [arr.length * 4]; // 最好情况 2*n-1 最坏情况 4*n-5 for(int i = 0; i < arr.length; i++){ data[i] = arr[i]; } // 也可用System.arraycopy(arr, 0, data, 0, arr.length),但需考虑深浅克隆; } public SegmentTree(E[] arr,Merger merger) { this.merger = merger; data = (E[])new Object [arr.length]; tree = (E[])new Object [arr.length * 4]; // 最好情况 2*n-1 最坏情况 4*n-5 for(int i = 0; i < arr.length; i++){ data[i] = arr[i]; } 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("error index"); } return data[index]; } private int leftChild(int index){ return 2 * index + 1; } private int rightChild(int index){ return 2 * index + 2; } private void buildSegmentTree(int treeIndex, int l , int r){ if(l == r){ // l == r 递归到叶子节点 tree[treeIndex] = data[l]; return; } int leftTreeIndex = leftChild(treeIndex); int rightTreeIndex = rightChild(treeIndex); int mid = l + (r - l) / 2; System.out.println(leftTreeIndex+"|"+rightTreeIndex+"|"+mid); buildSegmentTree(leftTreeIndex,l,mid); buildSegmentTree(rightTreeIndex,mid+1,r); tree[treeIndex] = merger.merge(tree[leftTreeIndex],tree[rightTreeIndex]); } 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); } public 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(queryL > mid){ return query(rightTreeIndex,mid+1,r,queryL,queryR); } if(queryR <= mid){ return query(leftTreeIndex,1,mid,queryL,queryR); } E rightResult = query(rightTreeIndex,mid+1,r,queryL,queryR); E leftResult = query(leftTreeIndex,1,mid,queryL,queryR); return merger.merge(leftResult,rightResult); } private void update(int index , E e ){ if(index < 0 || index >= data.length){ throw new IllegalArgumentException("error data"); } data[index] = e; updateTree(0,0,data.length-1,index,e); } private void updateTree(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) { updateTree(rightTreeIndex, mid + 1, r, index, e); } else //index <= mid { updateTree(leftTreeIndex, l, mid, index, e); } tree[treeIndex] = merger.merge(tree[leftTreeIndex], tree[rightTreeIndex]); } } interface Merger { E merge(E a,E b); }
测试类
public class Test1 {
public static void main(String[] args) {
testSegmentTree();
}
public static void testSegmentTree(){
Integer[] nums = new Integer[]{34, 65, 8, 10, 21, 86, 79, 30};
SegmentTree segTree = new SegmentTree<>(nums, new Merger() {
@Override
public Integer merge(Integer a, Integer b) {
//返回 a 和 b 的最大值
return Math.max(a, b);
}
});
// 查询区间 [2,5] 的最大值
System.out.println(segTree.query(4, 7));
}
}



