share Binary Index Tree(BIT) solution with O(n log n) time complexity and O(n) space


  • 0
    P
    class Solution {
        int lowbit(const int& t) {
            return t & (- t);
        }
        void add(vector<int> &tree, int i, int val) {
            for (; i < tree.size(); tree[i] += val, i += lowbit(i));
        }
        int sum(const vector<int> &tree, int i) {
            int res{0};
            for (; i > 0; res += tree[i], i -= lowbit(i));
            return res;
        }
    public:
        vector<int> countSmaller(vector<int>& nums) {
            vector<int> id{nums};
            std::sort(id.begin(), id.end());
            auto end_itr = unique(id.begin(), id.end());
            id.erase(end_itr, id.end());
            vector<int> index_tree(id.size() + 1, 0);
            vector<int> res(nums.size(), 0);
            for (int i = nums.size() - 1; i >= 0; -- i) {
                int index = lower_bound(id.begin(), id.end(), nums[i]) - id.begin() + 1;
                res[i] = sum(index_tree, index - 1);
                add(index_tree, index, 1);
            }
            return res;
        }
    };
    

Log in to reply
 

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