http://www.lintcode.com/en/problem/count-of-smaller-number-before-itself/\#

SegmentTree application. the key point of this is we have to keep the Tree to preserve only the element count before current index. so every iteration we search and then modify. note that 0 is the least number so can brainless skip and continue. and don't forget it is the count of the number less than the value in the array that we care about

public class Solution {
   /**
     * @param A: An integer array
     * @return: Count the number of element before this element 'ai' is 
     *          smaller than it and return count number array
     */ 

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

    public SegmentTreeNode build(int start, int end) {
        if (start == end) {
            return new SegmentTreeNode(start, start, 0);
        }

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

        SegmentTreeNode root = new SegmentTreeNode(left.start, right.end, 0);
        root.left = left;
        root.right = right;

        return root;
    }


    public int query(SegmentTreeNode root, int start, int end) {

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

        int mid = (root.start + root.end) / 2;

        if (start > mid) {
            return query(root.right, start, end);
        } else if (end <= mid) {
            return query(root.left, start, end);
        }

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

        return left + right;
    }


    public void modify(SegmentTreeNode root, int value) {
        if (root.start == root.end) {
            root.count += 1;
            return;
        }

        int mid = (root.start + root.end) / 2;
        if (value > mid) {
            modify(root.right, value);
        } else {
            modify(root.left, value);
        }

        root.count = root.left.count + root.right.count;
    }



    public ArrayList<Integer> countOfSmallerNumberII(int[] A) {
        // write your code here
        ArrayList<Integer> ans = new ArrayList<Integer>();
        if (A == null || A.length == 0) {
            return ans;
        }

        SegmentTreeNode root = build(0, 10000);
        modify(root, A[0]);
        ans.add(0);

        for (int i = 1; i < A.length; i++) {
            if (A[i] == 0) {
                ans.add(0);
                modify(root, A[i]);
                continue;
            }
            ans.add(query(root, 0, A[i] - 1));
            modify(root, A[i]);
        }

        return ans;


    }
}