นับจำนวนน้อยกว่าด้านขวาใน C++ (Count of Smaller Numbers After Self)

ภาพรวมปัญหา

ให้อาเรย์ nums สร้างอาเรย์ count ที่ count[i] = จำนวนตัวเลขที่น้อยกว่า nums[i] และอยู่ทางขวา (index > i)

ตัวอย่าง

[5,2,7,1] → [2,1,1,0]

วิธีแก้ปัญหา: BIT (Fenwick Tree) + Coordinate Compression

1. Normalize ค่า: ลบ min ออก +1 ให้เริ่มที่ 1
2. ใช้ BIT นับความถี่: update(index, +1), query(index) = prefix sum
3. วนจากขวาไปซ้าย: query(nums[i]-1) ได้จำนวนน้อยกว่า, แล้ว update(nums[i], +1)

โค้ด C++

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

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];
        for (int i = 1; i < n; i++) minn = min(minn, nums[i]);
        int maxx = 0;
        for (int i = 0; i < n; i++) {
            nums[i] = nums[i] - minn + 1;
            maxx = max(maxx, nums[i]);
        }
        vector<int> bit(maxx + 1);
        for (int i = n - 1; i >= 0; i--) {
            int num = nums[i] - 1;
            res[i] = query(num, bit);
            update(num + 1, bit, maxx);
        }
        return res;
    }
};

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

การวิเคราะห์ความซับซ้อน

• เวลา: O(n log n)
• พื้นที่: O(n)