Count Smaller elements

class Solution {
private:
    vector<int> BIT;
    int n;
    
    void update(int index, int val) {
        index++;
        while (index <= n) {
            BIT[index] += val;
            index += index & (-index);
        }
    }
    
    int query(int index) {
        int sum = 0;
        index++;
        while (index > 0) {
            sum += BIT[index];
            index -= index & (-index);
        }
        return sum;
    }
    
public:
    vector<int> constructLowerArray(vector<int>& arr) {
        n = arr.size();
        BIT.resize(n + 1, 0);
        
        vector<int> sortedArr = arr;
        sort(sortedArr.begin(), sortedArr.end());
        
        unordered_map<int, int> valueToIndex;
        for (int i = 0; i < n; i++) {
            valueToIndex[sortedArr[i]] = i;
        }
        
        vector<int> result(n);
        for (int i = n - 1; i >= 0; i--) {
            int index = valueToIndex[arr[i]];
            result[i] = query(index - 1);
            update(index, 1);
        }
        
        return result;
    }
};