手把手写一个集合框架（十二）补充篇SegmentTree

    线段树（Segment Tree）是一种将原来的数组转化为二叉树的一种结构，最经典的题目就是着色问题。

• 线段树的实现

• 构造函数

public class SegmentTree<E> {    
   private E[] date;    
   private E[] tree;    
   private Merger<E> merger;    
   SegmentTree(E[] arr,Merger<E> merger){        
        this.merger = merger;
        date = (E[])new Object[arr.length];        
        for(int i = 0 ; i < arr.length ; i ++)
             date[i] = arr[i];
        tree = (E[])new Object[4*arr.length];
        buildSegmentTree(0, 0, arr.length - 1);
}

• 基本属性

int getSize(){//获取数据长度
    return date.length;
}    

public E get(int index){//获取一个元素
   if(index<0 || index>getSize())       
      throw new IllegalArgumentException("index error!");     
   return date[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] = date[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 E query(int queryL, int queryR){
   /*返回区间[queryL, queryR]的值*/
  if(queryL<0||queryL>=date.length||
        queryR<0||queryR>=date.length||queryL>queryR)            
    throw new IllegalArgumentException("Index is illegal.");        
  return query(0, 0, date.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];
     /*
        treeIndex的节点分为[l...mid]和[mid+1...r]两部分
     */        
     int mid = l + (r - l) / 2;
     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);
}

• 更新某一下标的值

//将index位置的值，更新为epublic void update(int index, E e){        
    if(index < 0 || index >= data.length)            
      throw new IllegalArgumentException("Index is illegal");
    data[index] = e;
    update(0, 0, data.length - 1, index, e);
}    

/*
   在以treeIndex为根的线段树中更新index的值为e
*/

private void update(int treeIndex, int l, int r, int index, E e){
    if(l == r){
      tree[treeIndex] = e;            
          return;
    }        
    //treeIndex的节点分为[l...mid]和[mid+1...r]两部分
    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 // index <= mid
       set(leftTreeIndex, l, mid, index, e);
    tree[treeIndex] = merger.merge(tree[leftTreeIndex], 
                      tree[rightTreeIndex]);
}

• 总结

      线段树的用途很广泛，比如求某一区间的值，那么使用线段树效率高于其他数据结构的时间复杂度。

• 练习

  Leetcode 303. Range Sum Query - Immutable