离散化数组

树状数组遇到的新知识，离散化 参考题目

这题理解了很久，题解的正常思路是通过桶排序的方式统计当前先入桶的有多少比自己小，即桶排序中自己前一个位置的前缀和。进而通过树状数组优化前缀和到log(n)复杂度，又通过离散化将大范围的桶排序优化成连续的小数组排序，降低内存占用。
// 离散化方法

        sort(tmp.begin(), tmp.end());
        cout << "sorted: ";
        for (auto mm : tmp) {
            cout << mm << " ";
        }
        cout << endl;
        for (int &num : nums) {
            num = lower_bound(tmp.begin(), tmp.end(), num) - tmp.begin() + 1;
        }

个人理解，加了些注释

class BIT{
public:
    vector<int> tree;
    int n;

    BIT(int _n): n(_n), tree(_n+1) {}

    static int lowBit(int x) {
        return x & (-x);
    }

    int query(int x) {
        int ret = 0;

        while (x > 0) {
            ret += tree[x];
            x -= lowBit(x);
        }

        return ret;
    }

    void update(int x) {
        while (x <= n) {
            ++tree[x];
            x += lowBit(x);
        }
    }
};


class Solution{
public:
    int reversePairs(vector<int>& nums) {
        int n = nums.size();
        vector<int> tmp = nums;
        // 离散化数组，未排序的元素值置为在排序后的数组中的位置即为离散化
        sort(tmp.begin(), tmp.end());
        for (auto& num : nums) {
            // 为了避免0的lowbit操作失效进行加一操作
            num = lower_bound(tmp.begin(), tmp.end(), num) - tmp.begin() + 1;  
        }

        BIT bit(n);
        int ans = 0;
        for (int i = n - 1; i >= 0; --i) {
            ans += bit.query(nums[i] - 1);
            bit.update(nums[i]);
        }

        return ans;
    }
};