线段树

对于有一类的问题，我们主要关心的是线段(区间)，比如说查询一个区间[i, j]内的最大值，最小值等等。假设你有一个网站，你想查询某年(或某年以后)的用户访问量，消费最多的用户等等，这些都是在某个区间内进行查询，一般线段树的区间是固定的，不包含删除和添加的操作，只有查询和更新的操作
线段树 - 图1

线段树的表示

线段树 - 图2
现在如果假设有n个元素，用数组存储的话，需要多少空间呢
线段树 - 图3

  1. public class SegmentTree<E> {
  2.     private E[] tree;
  3.     private E[] data;
  5.     public SegmentTree(E[] arr) {
  6.         data = (E[]) new Object[arr.length];
  7.         for (int i = 0; i < arr.length; i++) {
  8.             data[i] = arr[i];
  9.         }
  11.         tree = (E[]) new Object[4 * data.length];
  12.     }
  14.     public int getSize() {
  15.         return data.length;
  16.     }
  17.     public E get(int index) {
  18.         if (index < 0 || index >= data.length) {
  19.             throw new IllegalArgumentException("参数错误");
  20.         }
  21.         return data[index];
  22.     }
  24.     private int leftChild(int index) {
  25.         return 2 * index + 1;
  26.     }
  27.     private int rightChild(int index) {
  28.         return 2 * index + 2;
  29.     }
  30. }

实现

创建线段树

下面就要根据数组来创建一棵线段树，我们的方法先创建下面的子线段树，然后由这些子线段树合并成大的线段树，以此类推
线段树 - 图4
在合并左右子树的过程中，我们不能写死合并的过程，具体怎么合并应该由业务决定，由用户去决定如何合并，所以合并的过程我们写一个接口，具体的实现由用户去实现

  1. public interface Merger<E> {
  2.     public E merge(E a, E b);
  3. }

然后我们在构造方法中添加创建线段树的过程(为了创建线段树，增加了一个辅助方法)

  1. private Merger<E> merger;
  2. //merger由用户传入 用户决定如何合并
  3. public SegmentTree(E[] arr, Merger<E> merger) {
  4.     this.merger = merger;
  6.     data = (E[]) new Object[arr.length];
  7.     for (int i = 0; i < arr.length; i++) {
  8.         data[i] = arr[i];
  9.     }
  11.     tree = (E[]) new Object[4 * data.length];
  12.     //构造线段树 创建根节点为0，范围为[0,data.length - 1]的线段树
  13.     buildSegmentTree(0, 0, data.length - 1);
  14. }
  16. //在treeIndex创建一棵[l,r]的线段树
  17. private void buildSegmentTree(int treeIndex, int l, int r) {
  18.     if (l == r) {
  19.         tree[treeIndex] = data[l];
  20.         return;
  21.     }
  23.     //l != r 那么就要创建子树的线段树
  24.     int leftTreeIndex = leftChild(treeIndex);
  25.     int rightTreeIndex = rightChild(treeIndex);
  26.     int mid = l + (r - l) / 2; //(l +r) / 2中l + r可能会大于int表示的范围从而溢出
  27.     buildSegmentTree(leftTreeIndex, l, mid);
  28.     buildSegmentTree(rightTreeIndex, mid + 1, r);
  30.     //融合的方法由用户传入
  31.     tree[treeIndex] = merger.merge(tree[leftTreeIndex],tree[rightTreeIndex]);
  32. }

为了方便我们打印出线段树，我们实现一个toString()方法

  1. @Override
  2. public String toString() {
  3.     StringBuilder res = new StringBuilder();
  4.     res.append("[");
  5.     for (int i = 0; i < tree.length; i++) {
  6.         if (tree[i] != null) {
  7.             res.append(tree[i]);
  8.         } else {
  9.             res.append("null");
  10.         }
  11.         if (i != tree.length - 1) {
  12.             res.append(", ");
  13.         }
  14.     }
  15.     res.append("]");
  16.     return res.toString();
  17. }

查询

线段树 - 图5
实现代码

  1. public E query(int queryL, int queryR) {
  2.     if (queryL < 0 || queryL >= data.length
  3.             || queryR < 0 || queryR >= data.length
  4.             || queryL > queryR) {
  5.         throw new IllegalArgumentException("参数错误");
  6.     }
  7.     return query(0, 0, data.length - 1, queryL, queryR);
  8. }
  9. private E query(int treeIndex, int l, int r, int queryL, int queryR) {
  10.     if (l == queryL && r == queryR) {
  11.         return tree[treeIndex];
  12.     }
  13.     int leftChildIndex = leftChild(treeIndex);
  14.     int rightChildIndex = rightChild(treeIndex);
  15.     int mid = l + (r - l) / 2;
  16.     if (queryL >= mid + 1) {
  17.         return query(rightChildIndex, mid+1, r, queryL, queryR);
  18.     } else if (queryR <= mid) {
  19.         return query(leftChildIndex, l, mid, queryL, queryR);
  20.     }
  21.     E leftResult = query(leftChildIndex, l, mid, queryL, mid);
  22.     E rightResult = query(rightChildIndex, mid + 1, r, mid + 1, queryR);
  23.     return merger.merge(leftResult, rightResult);
  24. }

更新

  1. public void set(int index, E e) {
  2.     if (index < 0 || index >= data.length) {
  3.         throw new IllegalArgumentException("参数错误");
  4.     }
  6.     set(0, 0, data.length - 1, index, e);
  7. }
  8. private void set(int treeIndex, int l, int r, int index, E e) {
  9.     if (l == r) {
  10.         tree[treeIndex] = e;
  11.         return;
  12.     }
  13.     int leftChildIndex = leftChild(treeIndex);
  14.     int rightChildIndex = rightChild(treeIndex);
  15.     int mid = l + (r - l) / 2;
  16.     if (index >= mid + 1) {
  17.         set(rightChildIndex, mid+1, r, index, e);
  18.     } else {
  19.         set(leftChildIndex, l, mid, index, e);
  20.     }
  22.     tree[treeIndex] = merger.merge(tree[leftChildIndex], tree[rightChildIndex]);
  23. }

完整代码

  1. public class SegmentTree<E>{
  2.     private E[] tree;
  3.     private E[] data;
  4.     private Merger<E> merger;
  6.     public SegmentTree(E[] arr, Merger<E> merger) {
  7.         this.merger = merger;
  9.         data = (E[]) new Object[arr.length];
  10.         for (int i = 0; i < arr.length; i++) {
  11.             data[i] = arr[i];
  12.         }
  14.         tree = (E[]) new Object[4 * data.length];
  15.         buildSegmentTree(0, 0, data.length - 1);
  16.     }
  18.     //在treeIndex创建一棵[l,r]的线段树
  19.     private void buildSegmentTree(int treeIndex, int l, int r) {
  20.         if (l == r) {
  21.             tree[treeIndex] = data[l];
  22.             return;
  23.         }
  25.         int leftTreeIndex = leftChild(treeIndex);
  26.         int rightTreeIndex = rightChild(treeIndex);
  28.         int mid = l + (r - l) / 2; //(l +r) / 2中l + r可能会大于int表示的范围从而溢出
  29.         buildSegmentTree(leftTreeIndex, l, mid);
  30.         buildSegmentTree(rightTreeIndex, mid + 1, r);
  32.         tree[treeIndex] = merger.merge(tree[leftTreeIndex],tree[rightTreeIndex]);
  33.     }
  35.     public E query(int queryL, int queryR) {
  36.         if (queryL < 0 || queryL >= data.length
  37.                 || queryR < 0 || queryR >= data.length
  38.                 || queryL > queryR) {
  39.             throw new IllegalArgumentException("参数错误");
  40.         }
  42.         return query(0, 0, data.length - 1, queryL, queryR);
  43.     }
  45.     private E query(int treeIndex, int l, int r, int queryL, int queryR) {
  46.         if (l == queryL && r == queryR) {
  47.             return tree[treeIndex];
  48.         }
  50.         int leftChildIndex = leftChild(treeIndex);
  51.         int rightChildIndex = rightChild(treeIndex);
  52.         int mid = l + (r - l) / 2;
  54.         if (queryL >= mid + 1) {
  55.             return query(rightChildIndex, mid+1, r, queryL, queryR);
  56.         } else if (queryR <= mid) {
  57.             return query(leftChildIndex, l, mid, queryL, queryR);
  58.         }
  60.         E leftResult = query(leftChildIndex, l, mid, queryL, mid);
  61.         E rightResult = query(rightChildIndex, mid + 1, r, mid + 1, queryR);
  63.         return merger.merge(leftResult, rightResult);
  64.     }
  67.     public void set(int index, E e) {
  68.         if (index < 0 || index >= data.length) {
  69.             throw new IllegalArgumentException("参数错误");
  70.         }
  72.         set(0, 0, data.length - 1, index, e);
  73.     }
  75.     private void set(int treeIndex, int l, int r, int index, E e) {
  76.         if (l == r) {
  77.             tree[treeIndex] = e;
  78.             return;
  79.         }
  80.         int leftChildIndex = leftChild(treeIndex);
  81.         int rightChildIndex = rightChild(treeIndex);
  82.         int mid = l + (r - l) / 2;
  83.         if (index >= mid + 1) {
  84.             set(rightChildIndex, mid+1, r, index, e);
  85.         } else {
  86.             set(leftChildIndex, l, mid, index, e);
  87.         }
  89.         tree[treeIndex] = merger.merge(tree[leftChildIndex], tree[rightChildIndex]);
  90.     }
  92.     public int getSize() {
  93.         return data.length;
  94.     }
  95.     public E get(int index) {
  96.         if (index < 0 || index >= data.length) {
  97.             throw new IllegalArgumentException("参数错误");
  98.         }
  99.         return data[index];
  100.     }
  102.     private int leftChild(int index) {
  103.         return 2 * index + 1;
  104.     }
  105.     private int rightChild(int index) {
  106.         return 2 * index + 2;
  107.     }
  109.     @Override
  110.     public String toString() {
  111.         StringBuilder res = new StringBuilder();
  112.         res.append("[");
  113.         for (int i = 0; i < tree.length; i++) {
  114.             if (tree[i] != null) {
  115.                 res.append(tree[i]);
  116.             } else {
  117.                 res.append("null");
  118.             }
  120.             if (i != tree.length - 1) {
  121.                 res.append(", ");
  122.             }
  123.         }
  124.         res.append("]");
  125.         return res.toString();
  126.     }
  127. }