线段树 - SegmentTree

为什么要使用线段树？
—— Range query

一类典型问题，染色问题。
每次在区间 「a，b」中挑选一个颜色进行粉刷。 求经过m次粉刷操作后，区间「i，j」上有多少种颜色？

线段树对区间查询有一些特殊设计，所以也称为区间树。

线段树是一棵二叉树，每个节点表示一个区间。 父节点是两个子节点的超集。

线段树不是完全二叉树，是平衡二叉树

查询的时间复杂度为 O(log N)。

递归创建线段树的过程， buildSegmentTree

public class SegmentTree<E> {

    private E[] data;
    private E[] tree;
    private Merger<E> merger;

    public SegmentTree(E[] arr, Merger merger){
        data = (E[]) new Object[arr.length];
        for(int i = 0; i < arr.length; i ++){
            data[i] = arr[i];
        }
        tree = (E[]) new Object[arr.length * 4];
        this.merger = merger;

        buildSegmentTree(0, 0, data.length-1);
    }
    // 在treeIndex 位置创建表示区间为[l...r]的线段树
    private void buildSegmentTree(int treeIndex, int l, int r){
        if(l == r){
            tree[treeIndex] = data[l];
            return;
        }else {
            int leftTreeIndex = leftChild(treeIndex);
            int rightTreeIndex = rightChild(treeIndex);
            int mid = l + (r-l)/2;
            buildSegmentTree(leftTreeIndex, l, mid);
            buildSegmentTree(rightTreeIndex, mid+1, r);

            // 综合两个孩子节点的信息， 使父节点是两个区间的加总结果。
            tree[treeIndex] = merger.merge( tree[leftTreeIndex], tree[rightTreeIndex]);
        }
    }

    ```

注意， 区间合并的归则不一定是求和，也可以是求最大，计数，去重计数。 
所以这里要放宽merge操作的逻辑，传入一个融合器接口——merger。 


查询函数的递归表示： 

```java
// 返回区间[queryL, queryR] 的值
    public E query(int queryL, int queryR){
        if(queryL < 0 || queryR < 0 || queryL >= data.length || queryR >= data.length)
            throw  new IllegalArgumentException("index error");

        return query(0, 0, data.length -1, queryL, queryR);
    }

    // 以treeId 为根的线段树「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;
        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);
        } else {
            // 与左子树 右子树都有关系
            E lResult = query(leftTreeIndex, l, mid, queryL, mid);
            E rResult = query(rightTreeIndex, mid+1, r, mid+1, queryR);
            return merger.merge(lResult, rResult);
        }
    }

    ```

空间复杂度， 4N。 
时间复杂度， 
- 创建树 O(N)
- 更新  O(log N)
- 查询  O(log N)



# 并查集 - Union Find Set