Segment Tree Build: http://www.lintcode.com/en/problem/segment-tree-build/#

• start > end 时 return。
• start == end 时 return leaf node
• divide and conquer, o(n)

private class SegmentTreeNode {
    public int start;
    public int end;
    public SegmentTreeNode left;
    public SegmentTreeNode right;

    public SegmentTreeNode(int start, int end) {
        this.start = start;
        this.end = end;
        this.left = null;
        this.right = null;
    }
}

public SegmentTreeNode build(int start, int end) {
    if (start > end) return null;

    SegmentTreeNode node = new SegmentTreeNode(start, end);
    if (start == end) return node;

    int mid = start + (end - start) / 2;
    node.left = build(start, mid);
    node.right = build(mid + 1, right);

    return node;
}

Segment Tree Build ii: http://www.lintcode.com/en/problem/segment-tree-build-ii/

• with a max attribute in node
• divide and conquer, o(n)
• start and end 是用来帮助划分区间的
• 因为需要 access leaf.left.max leaf.right.max 所以 需要在leaf 时 return 否则会有null pointer
• Step:
  • find the leaf, start == end
  • find mid, divide and conquer
  • node value

public SegmentTreeNode build(int[] A) {
    return buildHelper(A, 0, A.length - 1);
}

private SegmentTreeNode buildHelper(int[] A, int start, int end) {
    if (start > end) return null;
    if (start == end) return new SegmentTreeNode(start, end, A[start]);

    int mid = start + (end - start) / 2;
    SegmentTreeNode left = buildHelper(A, start, mid);
    SegmentTreeNode right = buildHelper(A, mid + 1, end);

    int max = Math.max(left.max, right.max);
    SegmentTreeNode node = new SegmentTreeNode(start, end, max);
    node.left = left;
    node.right = right;

    return node;
}

Segment Tree Modify: http://www.lintcode.com/en/problem/segment-tree-modify/

• divide and conquer, without return value 无返回值的分治
• 因为需要 access leaf.left.max leaf.right.max 所以 需要在 required leaf or before leaf 时 return 否则会有null pointer
• Step:
  • skip irrelevant node
  • find exact node, update value
  • update current node value

public void modify(SegmentTreeNode root, int index, int value) {
    if (root == null) return;
    // 要找的node 不在这里及以下
    if (index < root.start || index > root.end) return;

    // find and handle the leaf node
    // 需要 return 不然会有null pointer
    if (root.start == index && root.end == index) {
        root.max = value;
        return;
    }

    modify(root.left, index, value);
    modify(root.right, index, value);
    root.max = Math.max(root.left.max, root.right.max);    
}

Segment Tree Query: http://www.lintcode.com/en/problem/segment-tree-query/#

• 给你个范围(start, end. 理解为index) 返回最大值
• 一般情况的查找 即 for loop find value, o(n). 所以 频繁查找 segment tree 更优 o(logn)
• 当查询区间包含了当前node区间 (root.start == max(root.start, start) && root.end == min(root.end, end) 直接返回node value. e.g. (node: [2,4], query: [1,5] 则 可以直接返回node值)
• 当查询区间和当前node区间无交集时 (root.end < start || root.start > end) 直接返回 min
• 向下递归时 用最小区间 (收缩区间) max(start, root.start), min(end, root.end)
• Step:
  • skip irrelevant node
  • 收缩区间
  • find exact node
• cases:
  • total overlap: end >= root.end && start <= root.start return node.max
  • partial overlap: search both branches start = Math.max(start, root.start), end = Math.min(end, root.end)
  • no overlap: root.start > end || root.end < start return min / max

    public int query(SegmentTreeNode root, int start, int end) {
        // write your code here
        if (root == null) return Integer.MIN_VALUE;

        // no overlap
        if (start > root.end || end < root.start) return Integer.MIN_VALUE;

        // total overlap
        if (start <= root.start && end >= root.end) return root.max;

        // partial
        start = Math.max(start, root.start);
        end = Math.min (end, root.end);

        return Math.max(query(root.left, start, end), 
            query(root.right, start, end));
    }

Segment Tree Query ii: http://www.lintcode.com/en/problem/segment-tree-query-ii/#

• //给定区间(start to end value 值域, not index) 返回在这个区间里包含多少个 array里的数
• given interval, return how many non-zero numbers in this range
• Tree was built based on array, from min val to max val. For each node, count is used to denote how many numbers in this val range
• 这里的interval 理解为value (值域) 而不是index (范围)

public int query(SegmentTreeNode root, int start, int end) {
        if(root == null) return 0;
        if(end < root.start) return 0;
        if(start > root.end) return 0;

        start = Math.max(start, root.start);
        end = Math.min(end, root.end);

        if(root.start == start && root.end == end) return root.count;

        int left = query(root.left, start, end);
        int right = query(root.right, start, end);

        return left + right;
    }