# Easy to code O(n log(n)) solution using Fenwick Tree

• 	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);
}
}
};

• Thanks for the link! Also your method avoids shifting the input numbers to be positive! Smart!

• This post is deleted!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.