class Solution {
public:
vector<int> countSmaller(vector<int>& nums) {
int n = nums.size();
vector<int> tree(n + 1, 0);
int indices[n];
for (int i = 0; i < n; ++i) indices[i] = i;
sort(indices, indices + n, [&nums](const int& i, const int& j) { return nums[i] < nums[j]  (nums[i] == nums[j] && i < j); });
vector<int> counts(n);
for (int i = 0; i < n; ++i) {
int index = indices[i];
counts[index] = i  read(index, tree, n);
update(index, 1, tree, n);
}
return counts;
}
int read(int idx, const vector<int>& tree, int n){
++idx;
int sum = 0;
while (idx > 0){
sum += tree[idx];
idx = (idx & idx);
}
return sum;
}
void update(int idx, int val, vector<int>& tree, int n){
++idx;
while (idx <= n){
tree[idx] += val;
idx += (idx & idx);
}
}
};
Easy to code O(n log(n)) solution using Fenwick Tree


Fenwick tree (or binary indexed tree) taken from here: https://www.topcoder.com/community/datascience/datasciencetutorials/binaryindexedtrees/

https://leetcode.com/discuss/80870/implementationinspiredbinaryindexdealduplicatenumber
CAN YOU HELP ME ?