Đếm số nhỏ hơn bên phải (Count of Smaller Numbers After Self) trong C++

Cho mảng nums, trả về mảng count với count[i] = số phần tử nhỏ hơn nums[i] ở bên phải (chỉ số > i).

Ví dụ

nums = [5,2,7,1] → count = [2,1,1,0]

• 5: bên phải có 2,1 → 2 số nhỏ hơn
• 2: bên phải có 1 → 1 số
• 7: bên phải có 1 → 1 số
• 1: bên phải rỗng → 0

Thuật toán: BIT (Fenwick Tree) + Compression

1. Nén tọa độ: Dịch mảng về chỉ số dương bắt đầu từ 1 (trừ min + 1).
2. Duyệt từ phải sang trái:
   • Query BIT: số phần tử đã thấy < current value.
   • Update BIT: thêm current value.

Cài đặt C++

#include <bits/stdc++.h>
using namespace std;

void print_vector(vector<int> v) {
    cout << "[";
    for (int i = 0; i < v.size(); i++) cout << v[i] << ", ";
    cout << "]" << endl;
}

class Solution {
public:
    void update(int index, vector<int>& bit, int n) {
        while (index <= n) {
            bit[index]++;
            index += index & (-index);
        }
    }

    int query(int index, vector<int> bit) {
        int ans = 0;
        while (index > 0) {
            ans += bit[index];
            index -= index & (-index);
        }
        return ans;
    }

    vector<int> countSmaller(vector<int>& nums) {
        int n = nums.size();
        vector<int> res(n);
        if (!n) return res;
        int minn = nums[0], maxx = 0;
        for (int i = 1; i < n; i++) minn = min(minn, nums[i]);
        for (int i = 0; i < n; i++) {
            nums[i] = nums[i] - minn + 1;
            maxx = max(maxx, nums[i]);
        }
        vector<int> bit(maxx + 1, 0);
        for (int i = n - 1; i >= 0; i--) {
            int num = nums[i] - 1;
            int x = query(num, bit);
            res[i] = x;
            update(num + 1, bit, maxx);
        }
        return res;
    }
};

int main() {
    Solution ob;
    vector<int> v = {5, 2, 7, 1};
    print_vector(ob.countSmaller(v));
    return 0;
}

Độ phức tạp

• Thời gian: O(n log n) — n lần query/update BIT.
• Không gian: O(n) — BIT + mảng kết quả.

Input / Output

Input:  [5,2,7,1]
Output: [2, 1, 1, 0]