【leetcode】315. 计算右侧小于当前元素的个数（count-of-smaller-numbers-after-self）（树状数组）[困难]

链接

https://leetcode-cn.com/problems/count-of-smaller-numbers-after-self/

耗时

解题：1 day
题解：11 min

题意

给定一个整数数组 nums，按要求返回一个新数组 counts。数组 counts 有该性质： counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。

思路

死活想不出来，晚上看了标签有树状数组，还是没想出来，最后看了一眼题解，看到计数前缀和那秒懂，菜的吐血。
从后向前遍历，用一个树状数组记录当前每个数字出现的次数，这里用树状数组是为了快速单点修改求前缀和，因为当前数字之前的小于它的数字出现的次数的和就是所求的右侧小于当前元素的数量。
醉了，，，，

时间复杂度： O ( m l o g n ) O(mlogn) O(mlogn)，m=nums.size(); n=50010;

AC代码

class Solution {
public:
    constexpr static int n = 50010;
    int bit[n];

    int sum(int i) {
        int s=0;
        while(i>0) {
            s += bit[i];
            i -= i & -i;
        }
        return s;
    }

    void add(int i,int x) {
        while(i<=n) {
            bit[i] += x;
            i += i& -i;
        }
    }
    
    vector<int> countSmaller(vector<int>& nums) {
        int m = nums.size();
        vector<int> counts(m, 0);
        for(int i = m-1; i >= 0; --i) {
            add(nums[i]+25000, 1);
            counts[i] = sum(nums[i]+25000-1);
        }
        return counts;
    }
};