线段树

 201一 线段树的构造

/**
 * Definition of SegmentTreeNode:
 * public class SegmentTreeNode {
 *     public int start, end;
 *     public SegmentTreeNode left, right;
 *     public SegmentTreeNode(int start, int end) {
 *         this.start = start, this.end = end;
 *         this.left = this.right = null;
 *     }
 * }
 */
public class Solution {
    /**
     *@param start, end: Denote an segment / interval
     *@return: The root of Segment Tree
     */
    public SegmentTreeNode build(int start, int end) {
        // write your code here
        if (start > end){
            return null;
        }
        SegmentTreeNode root = new SegmentTreeNode(start, end);
        if (start != end){
            int mid = (start + end) / 2;
            root.left = build(start, mid);
            root.right = build(mid + 1, end);
        }
        return root;
    }
}

    public SegmentTreeNode build(int[] A) {
        // write your code here
    }
    public SegmentTreeNode buildTree(int start, int end, int[] A){
        if (start > end) return null;
        if (start == end){
            return new SegmentTreeNode(start, end, A[start]);
        }
        SegmentTreeNode node = new SegmentTreeNode(start, end, A[start]);
        int mid = (start + end) / 2;
        node.left = this.buildTree(start, mid, A);
        node.left = this.buildTree(mid + 1, end, A);
        if (node.left != null && node.left.max > node.max){
            node.max = node.left.max;
        }
        if (node.right != null && node.right.max > node.max){
            node.max = node.right.max;
        }
        return node;
    }

二 线段树的操作

202线段树的查询

    public int query(SegmentTreeNode root, int start, int end) {
        // write your code here
        if (root.start == start && root.end == end){
            return root.max;
        }
        int mid = (root.start + root.end) / 2;
        int leftM = Integer.MIN_VALUE, rightM = Integer.MIN_VALUE;
        if (start <= mid){
            if (mid < end){
                leftM =  query(root.left, start, mid);
            }else {
                leftM = query(root.left, start, end);
            }
        } 
        if (mid < end){
            if (start <= mid){
                rightM = query(root.right, mid + 1, end);
            }else{
                rightM = query(root.right, start, end);
            }
        }
        return Math.max(leftM, rightM);
    }

    public int query(SegmentTreeNode root, int start, int end) {
        // write your code here
        if (root == null || start > end){
            return 0;
        }
        if (root.start == start && root.end == end){
            return root.count;
        }
        int mid = (root.left + root.right) / 2;
        int leftc = 0, rightc = 0;
        if (start <= mid){
            if (mid < end) {
                leftc = query(root.left, start, mid);
            } else {
                leftc = query(root.right, start, end);
            }
        }
        if (end > mid){
            if (start > mid){
                rightc = query(root.left, start, end);
            } else {
                rightc = query(root.right, mid + 1, end);
            }
        }
        return leftc + rightc;
    }

 203线段树的修改

    public void modify(SegmentTreeNode root, int index, int value) {
        // write your code here
        if (root.start == index && root.end == index){
            root.max = val;
        }
        int mid = (root.left + root.right) / 2;
        if (index >= root.start && index <= mid){
            modify(root.left, index, value);
        }
        if (index > mid && index < root.right){
            modify(root.right, index, value);
        }
        root.max = Math.max(root.left.max, root.right.max);
    }

205 区间最小数

public class Solution {
    /**
     *@param A, queries: Given an integer array and an query list
     *@return: The result list
     */
     
         
    public SegmentTreeNode build(int start, int end, int[] A){
        if (start > end){
            return null;
        }
        SegmentTreeNode root = new SegmentTreeNode(start, end, Integer.MAX_VALUE);
        if (start != end){
            int mid = (start + end) / 2;
            root.left = build(start, mid, A);
            root.right = build(mid + 1, end, A);
            root.min = Math.min(root.left.min, root.right.min);
        } else {
            root.min = A[start];
        }
        return root;
    }
    
    public int query(SegmentTreeNode root, int start, int end){
        if (root.start == start && root.end == end){
            return root.min;
        }
        int mid = (root.start + root.end) / 2;
        int leftm = Integr.MAX_VALUE, rightm = Integr.MAX_VALUE;
        if (start < mid){
            if (end < mid){
                leftm = query(root.left, start, end);
            } else {
                leftm = query(root.left, start, mid);
            }
        }
        if (end > mid){
            if (start > mid){
                rightm = query(root.right, start, end);
            } else {
                rightm = query(root.right, mid + 1, end);
            }
        }
        return Math.min(leftm, rightm);
    }
    public ArrayList<Integer> intervalMinNumber(int[] A, 
                                                ArrayList<Interval> queries) {
        // write your code here
        SegmentTreeNode root = build(0, A.length - 1, A);
        ArrayList<Integer> list = new ArrayList<>();
        for (Interval i : queries){
            list.add(query(root, i.start, i.end)
        }
    }
}
class SegmentTreeNode{
    public int start;
    public int end;
    public int min;
    public SegmentTreeNode left;
    public SegmentTreeNode right;
    public SegmentTreeNode(int start, int end, int min){
        this.start = start; this.end = end; this.min = min;
    }

三  线段树的优化

四 线段树的应用