数据结构-非线性结构-树形结构：有序树 -＞二叉树 -＞平衡二叉树 -＞线段树 (Segment Tree) / 区间树【不是完全二叉树；用于处理区间类数据】【基于静态数组/链表】【竞赛】

本文主要是介绍数据结构-非线性结构-树形结构：有序树 -＞二叉树 -＞平衡二叉树 -＞线段树 (Segment Tree) / 区间树【不是完全二叉树；用于处理区间类数据】【基于静态数组/链表】【竞赛】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

平衡二叉树（AVL树）：当且仅当任何节点的两棵子树的高度差不大于1的二叉树；

在这里插入图片描述

线段树的代码实现

SegmentTree.java

/*** 线段树** @author whx* @version 2018/8/25*/
public class SegmentTree<E> {/**普通数据*/private E[] data;/**树结构数据*/private E[] tree;/**融合器*/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]的线段树** @param treeIndex* @param left* @param right* @return void* @author whx* @version 2018/8/25*/private void buildSegmentTree(int treeIndex, int left, int right) {if(left == right){tree[treeIndex] = data[left];return;}int leftTreeIndex = leftChild(treeIndex);int rightTreeIndex = rightChild(treeIndex);int mid = left + (right - left) / 2;buildSegmentTree(leftTreeIndex,left,mid);buildSegmentTree(rightTreeIndex,mid + 1,right);//融合两个元素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];}/*** 查找用数组实现的完全二叉树中该索引下节点的左孩子节点的索引** @param index* @return int* @author whx* @version 2018/8/19*/public int leftChild(int index){return (index * 2) + 1;}/*** 查找用数组实现的完全二叉树中该索引下节点的右孩子节点的索引** @param index* @return int* @author whx* @version 2018/8/19*/public int rightChild(int index){return (index * 2) + 2;}/*** 查询区间[start...end]的值** @param start* @param end* @return E* @author whx* @version 2018/8/25*/public E query(int start, int end){if(start < 0 || start > data.length ||end < 0 || end > data.length ||start > end){throw new IllegalArgumentException("Index is illegal.");}return query(0, 0, data.length-1, start, end);}/*** 查询在以treeIndex为根的线段树区间为[l...r]的范围中，区间[start...end]的值** @param treeIndex* @param l* @param r* @param start* @param end* @return E* @author whx* @version 2018/8/25*/private E query(int treeIndex, int l, int r, int start, int end){if(l == start && r == end){return tree[treeIndex];}int middle = l + (r - l) / 2;int leftTreeIndex = leftChild(treeIndex);int rightTreeIndex = rightChild(treeIndex);if(start >= middle + 1){return query(rightTreeIndex,middle+1,r,start,end);}else if(end <= middle){return query(leftTreeIndex,l,middle,start,end);}E leftResult = query(leftTreeIndex, l, middle, start, middle);E rightResult = query(rightTreeIndex, middle + 1, r, middle + 1, end);return merger.merge(leftResult,rightResult);}/*** 更新index位置的元素为e** @param index* @param e* @return void* @author whx* @version 2018/8/26*/public void set(int index, E e){if(index < 0 || index >= data.length){throw new IllegalArgumentException("Index is illegal.");}set(0,0,data.length - 1,index,e);}/*** 更新在以treeIndex为根的线段树区间为[l...r]的范围中位置为index的值** @param treeIndex* @param l* @param r* @param index* @param e* @return void* @author whx* @version 2018/8/26*/private void set(int treeIndex, int l, int r, int index, E e){if(l == r){tree[treeIndex] = e;return;}int middle = l + (r - l) / 2;int leftTreeIndex = leftChild(treeIndex);int rightTreeIndex = rightChild(treeIndex);if(index >= middle + 1){set(rightTreeIndex,middle+1,r,index,e);}else if(index <= middle){set(leftTreeIndex,l,middle,index,e);}tree[treeIndex] = merger.merge(tree[leftTreeIndex], tree[rightTreeIndex]);}@Overridepublic String toString() {StringBuilder result = new StringBuilder();result.append("SegmentTree: [");for (int i = 0; i < tree.length; i++) {if (tree[i] != null){result.append(tree[i]);}else {result.append("null");}if (i != tree.length - 1) {result.append(",");}else {result.append("]");}}return result.toString();}
}

Merger.java

/*** 融合器** @author whx* @version 2018/8/25*/
public interface Merger<E> {/*** 融合两个元素** @param a* @param b* @return E* @author whx* @version 2018/8/25*/E merge(E a, E b);
}

Main.java

/*** @author whx* @version 2018/8/25*/
public class Main {public static void main(String[] args) {SegmentTree<Integer> segmentTree = new SegmentTree<Integer>(new Integer[]{-2, 0, 3, -5, 2, -1}, (a, b) -> a + b);System.out.println(segmentTree.toString());System.out.println(segmentTree.query(2, 4));System.out.println(segmentTree.query(0, 4));System.out.println(segmentTree.query(1, 4));System.out.println(segmentTree.query(3, 4));segmentTree.set(0, 20);System.out.println(segmentTree.toString());}
}