Lintcode: Count of Smaller Number before itself

也用到了线段树，但是更绕一些。最后一个测试超时了，需要思考。

public class Solution {
    public ArrayList<Integer> countOfSmallerNumberII(int[] A) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        if (A == null || A.length == 0) {
            return res;
        }
        MaxTreeNode root = build(A, 0, A.length - 1);
        for (int i = 0; i < A.length; i++) {
            res.add(getVal(root, i, A[i]));
        }
        return res;
    }
    
    private int getVal(MaxTreeNode root, int end, int val) {
        if (root == null || root.start > end) {
            return 0;
        }
        if (root.start == root.end || root.end >= end) {
            if (root.max < val)
                return root.end - root.start + 1;
        }
        return getVal(root.left, end, val) + getVal(root.right, end, val);
    }
    
    private MaxTreeNode build(int[] a, int start, int end) {
        if (start > end) {
            return null;
        }
        if (start == end) {
            return new MaxTreeNode(start, start, a[start]);
        }
        MaxTreeNode root = new MaxTreeNode(start, end);
        root.left = build(a, start, (start + end) / 2);
        root.right = build(a, (start + end) / 2 + 1, end);
        int max = 0;
        if (root.left == null) {
            root.max = root.right.max;
        } else if (root.right == null) {
            root.max = root.left.max;
        } else {
            root.max = Math.max(root.left.max, root.right.max);
        }
        return root;
    }
    class MaxTreeNode {
        int start;
        int end;
        int max;
        MaxTreeNode left;
        MaxTreeNode right;
        public MaxTreeNode(int start, int end) {
            this.start = start;
            this.end = end;
        }
        
        public MaxTreeNode(int start, int end, int max) {
            this(start, end);
            this.max = max;
        }
    }
}