Lintcode 249. Count of Smaller Number before itself

Give you an integer array (index from 0 to n-1, where n is the size of this array, data value from 0 to 10000) . For each element Ai in the array, count the number of element before this element Ai is smaller than it and return count number array.

Example

Example 1:

Input:
[1,2,7,8,5]
Output:
[0,1,2,3,2]

Example 2:

Input:
[7,8,2,1,3]
Output:
[0,1,0,0,2]

Clarification

Before you do this, you'd better complete the following three questions： Segment Tree Build， Segment Tree Query II，and Count of Smaller Number before itself I 。

Notice

We suggest you finish problem Segment Tree Build, Segment Tree Query II and Count of Smaller Number first.

Code (Java):

public class Solution {
    /**
     * @param A: an integer array
     * @return: A list of integers includes the index of the first number and the index of the last number
     */
    public List<Integer> countOfSmallerNumberII(int[] A) {
        // write your code here
        List<Integer> ans = new ArrayList<>();
        if (A == null || A.length == 0) {
            return ans;
        }

        SegmentTree segmentTree = new SegmentTree();
        segmentTree.build(0, 10000);

        for (int num : A) {
            int count = segmentTree.query(0, num - 1);
            ans.add(count);
            segmentTree.modify(num, 1);
        }
        return ans;
    }
}

class SegmentTree {
    SegmentTreeNode root = null;

    public void build(int start, int end) {
        root = buildHelper(start, end);
    }

    public int query(int start, int end) {
        return queryHelper(root, start, end);
    }

    public void modify(int index, int value) {
        modifyHelper(root, index, value);
    }

    private void modifyHelper(SegmentTreeNode root, int index, int value) {
        if (root == null) {
            return;
        }

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

        int mid = root.start + (root.end - root.start) / 2;
        if (index <= mid) {
            modifyHelper(root.left, index, value);
        } else {
            modifyHelper(root.right, index, value);
        }

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

    private int queryHelper(SegmentTreeNode root, int start, int end) {
        if (root == null || start > end) {
            return 0;
        }

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

        int mid = root.start + (root.end - root.start) / 2;
        int leftCount = queryHelper(root.left, Math.max(start, root.start), Math.min(mid, end));
        int rightCount = queryHelper(root.right, Math.max(mid + 1, start), Math.min(root.end, end));

        return leftCount + rightCount;
    }

    private SegmentTreeNode buildHelper(int start, int end) {
        if (start > end) {
            return null;
        }
        
        if (start == end) {
            return new SegmentTreeNode(start, start, 0);
        }

        int mid = start + (end - start) / 2;
        SegmentTreeNode leftChild = buildHelper(start, mid);
        SegmentTreeNode rightChild = buildHelper(mid + 1, end);

        SegmentTreeNode root = new SegmentTreeNode(start, end, leftChild.count + rightChild.count);
        root.left = leftChild;
        root.right = rightChild;

        return root;
    }

}

class SegmentTreeNode {
    int start, end;
    SegmentTreeNode left, right;
    int count;

    public SegmentTreeNode(int start, int end, int count) {
        this.start = start;
        this.end = end;
        this.count = count;
    }
}