Segment Tree Note

线段树是什么？

线段树是一种高级数据结构，也是一种树结构，准确的说是二叉树。它能够高效的处理区间修改查询等问题。

基本操作

• 线段树的构建 http://www.lintcode.com/en/problem/segment-tree-build/
• 线段树的修改 http://www.lintcode.com/en/problem/segment-tree-modify/
• 线段树的查询 http://www.lintcode.com/en/problem/segment-tree-query/

经典问题：

操作一:给序列的第i个数加上X (X可以为负数)

操作二:询问序列中最大的数是什么? 格式query(start, end)，表示区间[start, end]内，最大值是多少？

Example:

1. How to build a segment tree with maxVal in the interval

/**
 * Definition of SegmentTreeNode:
 * public class SegmentTreeNode {
 *     public int start, end, max;
 *     public SegmentTreeNode left, right;
 *     public SegmentTreeNode(int start, int end, int max) {
 *         this.start = start;
 *         this.end = end;
 *         this.max = max
 *         this.left = this.right = null;
 *     }
 * }
 */

public class Solution {
    /**
     * @param A: a list of integer
     * @return: The root of Segment Tree
     */
    public SegmentTreeNode build(int[] A) {
        if (A == null || A.length == 0) {
            return null;
        }
        
        return helper(A, 0, A.length - 1);
    }
    
    private SegmentTreeNode helper(int[] A, int left, int right) {
        if (left > right) {
            return null;
        }
        
        if (left == right) {
            SegmentTreeNode cur = new SegmentTreeNode(left, right, A[left]);
            return cur;
        }
        
        SegmentTreeNode leftNode = helper(A, left, (right + left) / 2);
        SegmentTreeNode rightNode = helper(A, (left + right) / 2 + 1, right);
        
        int maxVal = Integer.MIN_VALUE;
        if (leftNode != null) {
            maxVal = Math.max(maxVal, leftNode.max);
        }
        
        if (rightNode != null) {
            maxVal = Math.max(maxVal, rightNode.max);
        }
        
        SegmentTreeNode cur = new SegmentTreeNode(left, right, maxVal);
        cur.left = leftNode;
        cur.right = rightNode;
        
        return cur;
    }
}