Segment Tree


  • 0
    H
    1. Sort nums and map them to their id. So large id represents large number.
    2. Build a segment tree from 0 to max id. Segment tree is used for counting sum of interval in O(logn).
    3. for num from right to left:
      count sum of [0, id - 1].
      insert number.
    class Solution {
    public:
        struct node
        {
            int l,r,n;
        }tree[50005<<2];
        void build(int l, int r, int now)
        {
            tree[now].l = l;
            tree[now].r = r;
            tree[now].n = 0;
            if(l == r) return ;
            int mid = (l + r) >> 1;
            build(l, mid, now << 1);
            build(mid + 1, r, now << 1 | 1);
        }
        void insert(int id, int now)
        {
            tree[now].n++;
            if(tree[now].l == tree[now].r) return ;
            int mid = (tree[now].l + tree[now].r) >> 1;
            if(id <= mid) insert(id, now << 1);
            else insert(id, now << 1 | 1);
        }
        int query(int l, int r, int now)
        {
            if(tree[now].l == l && tree[now].r == r) return tree[now].n;
            int mid = (tree[now].l + tree[now].r) >> 1;
            if(l > mid) return query(l, r, now << 1 | 1);
            else if(r <= mid) return query(l, r, now << 1);
            else return query(l, mid, now << 1) + query(mid + 1, r, now <<1 | 1);        
        }
        vector<int> countSmaller(vector<int>& nums) 
        {        
            vector<int> sorted = nums;      
            sort(sorted.begin(), sorted.end());
            unordered_map<int, int> mp;
            for(int i = 0; i < sorted.size(); i++) mp[sorted[i]] = i + 1;
            build(0, sorted.size(), 1);
            for(int i = nums.size() - 1; i >= 0; i--)
            {
                int id = mp[nums[i]];
                nums[i] = query(0, id - 1, 1);
                insert(id, 1);
            }
            return nums;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.