LintCode 249: Count of Smaller Number before itself (线段树经典题！)

1. 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.

解法1：线段树

想了一下，这个题目和248不一样。好像只能用线段树和树状数组解。

代码如下:

struct SgMtTreeNode {
    int start, end, count;
    SgMtTreeNode *left, *right;
    SgMtTreeNode(int s = 0, int e = 0, int c = 0) : start(s), end(e), count(c) {
        left = NULL;
        right = NULL;
    }
};

class Solution {
public:
    /**
     * @param A: an integer array
     * @return: A list of integers includes the index of the first number and the index of the last number
     */
    vector<int> countOfSmallerNumberII(vector<int> &A) {
        int n = A.size();
        if (n <= 0) return vector<int>();
        
        vector<int> result;
        
        SgMtTreeNode * root = build(0, 10000);  
        
        for (int i = 0; i < n; ++i) {
            insert(root, A[i]);
            result.push_back(query(root, A[i] - 1));
        }
        
        return result;
    }


private:
    SgMtTreeNode * build(int start, int end) {
        if (start > end) return NULL;
        SgMtTreeNode * root = new SgMtTreeNode(start, end, 0);
        if (start == end) return root;
        int mid = start + (end -  start) / 2;
        root->left = build(start, mid);
        root->right = build(mid + 1, end);
        return root;
    }

    int query(SgMtTreeNode * root, int target) {
        if (!root) return 0;
        if (target >= root->end) return root->count;
        if (target < root->start) return 0;
        return query(root->left, target) + query(root->right, target);
    }
    
    void insert(SgMtTreeNode * root, int value) {
        if (!root) return;
        if (value == root->start && value == root->end) {
            root->count++;
            return;
        } 
        if (root->left && value <= root->left->end) {
            insert(root->left, value);
        }
        if (root->right && value >= root->right->start) {
            insert(root->right, value);
        }
        root->count++;
    }
};

           

注意：

1. insert()也可以写成如下形式。稍有冗余。

void insert(SgMtTreeNode * root, int value) {
        if (!root) return;
        if (value == root->start && value == root->end) {
            root->count++;
            return;
        } 
        if (root->left && value >= root->left->start && value <= root->left->end ) {
            insert(root->left, value);
        }
        if (root->right && value >= root->right->start && value <= root->right->end) {
            insert(root->right, value);
        }
        root->count++;
    }
           

2）不管是query还是insert，value都是和某个节点的start和end比，而不是和这个节点本身的count(或max,min比)。

3）在countOfSmallerNumberII()里面的query()要用A[i]-1，记住不是A[i]。

4）这题与LintCode 248唯一不同就是在countOfSmallerNumberII()里面，这题一边insert一边query，而248是一口气全部insert，然后一个一个query。

解法2：树状数组

TBD