[leetcode 315] 计算右侧小于当前元素的个数

题目： https://leetcode.cn/problems/count-of-smaller-numbers-after-self/description/

暴力 for 循环肯定会超时。

第一种标准解法是归并排序，但是这样依旧超时😨

class Solution {
public:
    vector<int> counts;
    vector<int> index;
    vector<int> tmpIndex;
    void merge_sort(vector<int>& nums, vector<int>& tmp, int start, int end) {
        if (start >= end) {
            return ;
        }
        int mid = (start + end) / 2;
        int start1 = start, end1 = mid;
        int start2 = mid+1, end2 = end;
        merge_sort(nums, tmp, start1, end1);
        merge_sort(nums, tmp, start2, end2);
        int i = start1, j = start2, k = start;
        while (i <= end1 && j <= end2) {
            if (nums[i] <= nums[j]) {
                tmpIndex[k] = index[i];
                tmp[k++] = nums[i++];
            }
            else {
                tmpIndex[k] = index[j];
                tmp[k++] = nums[j++];
                for (int n = i; n <= end1; n++) {
                    counts[index[n]]++;
                }
            }
        }
        while (i <= end1) {
            tmpIndex[k] = index[i];
            tmp[k++] = nums[i++];
        }
        while (j <= end2) {
            tmpIndex[k] = index[j];
            tmp[k++] = nums[j++];
        }
        for (int n = start; n <= end; n++) {
            nums[n] = tmp[n];
            index[n] = tmpIndex[n];
        }
    }
    vector<int> countSmaller(vector<int>& nums) {
        int len = nums.size();
        vector<int> tmp(len);
        counts = vector<int>(len, 0);
        index = vector<int>(len);
        tmpIndex = vector<int>(len);
        for (int i = 0; i < len; i++) {
            index[i] = i;
        }
        merge_sort(nums, tmp, 0, len-1);
        return counts;
    }
};

其实完全可以只排列下标，像下面这样（不过依旧超时）

class Solution {
public:
    vector<int> counts;
    vector<int> index;
    vector<int> tmpIndex;
    void merge_sort(vector<int>& nums, int start, int end) {
        if (start >= end) {
            return ;
        }
        int mid = (start + end) / 2;
        int start1 = start, end1 = mid;
        int start2 = mid+1, end2 = end;
        merge_sort(nums, start1, end1);
        merge_sort(nums, start2, end2);
        int i = start1, j = start2, k = start;
        while (i <= end1 && j <= end2) {
            if (nums[index[i]] <= nums[index[j]]) {
                tmpIndex[k++] = index[i++];
            }
            else {
                tmpIndex[k++] = index[j++];
                for (int n = i; n <= end1; n++) {
                    counts[index[n]]++;
                }
            }
        }
        while (i <= end1) {
            tmpIndex[k++] = index[i++];
        }
        while (j <= end2) {
            tmpIndex[k++] = index[j++];
        }
        for (int n = start; n <= end; n++) {
            index[n] = tmpIndex[n];
        }
    }
    vector<int> countSmaller(vector<int>& nums) {
        int len = nums.size();
        vector<int> tmp(len);
        counts = vector<int>(len, 0);
        index = vector<int>(len);
        tmpIndex = vector<int>(len);
        for (int i = 0; i < len; i++) {
            index[i] = i;
        }
        merge_sort(nums, 0, len-1);
        return counts;
    }
};

果然，还是要靠树状数组解决。树状数组参考这里：https://www.cnblogs.com/xenny/p/9739600.html

什么是树状数组？

黑色框是原数组 A，红色框是树状数组 C。树状数组存储了前缀和，关系是：

C[1] = A[1];
C[2] = A[1] + A[2];
C[3] = A[3];
C[4] = A[1] + A[2] + A[3] + A[4];
C[5] = A[5];
C[6] = A[5] + A[6];
C[7] = A[7];
C[8] = A[1] + A[2] + A[3] + A[4] + A[5] + A[6] + A[7] + A[8];

什么是 lowbit ？

对于 x&(-x)，其结果为

• x 为零，结果为零；
• x 为奇数，结果为 1；
• x 为偶数，且是 2 的幂，结果为 x；
• x 为偶数，但不是 2 的幂，结果为 x 的因子中 2 的最大次方；

为什么树状数组的大小是 n+1 ?

因为 0 号位置不能用，0&(-0) = 0

class Tree {
public: 
    vector<int> tree;
    int n;
    Tree (int n_) : tree(vector<int>(n_+1,0)), n(n_) {}
    int lowbit(int x) {
        return x & (-x);
    }
    void update(int x) {
        while (x <= n) {
            ++tree[x];
            x += lowbit(x);
        }
    }
    int qurry(int x) {
        int ret = 0;
        while (x > 0) {
            ret += tree[x];
            x -= lowbit(x);
        }
        return ret;
    }
};

class Solution {
public:
    vector<int> countSmaller(vector<int>& nums) {
        int len = nums.size();
        vector<int> tmp(nums);
        sort(tmp.begin(), tmp.end());
        for (int& num : nums) {
            num = lower_bound(tmp.begin(), tmp.end(), num) - tmp.begin() + 1;
        }
        Tree tree(len);
        vector<int> ans(len);
        for (int i = len - 1; i >= 0; i--) {
            int x = nums[i];
            ans[i] = tree.qurry(x - 1);
            tree.update(x);
        }
        return ans;
    }
};