1、树状数组

具体实现可参考LeetCode-剑指51-数组中的逆序对。考虑到数组的长度范围过大，我们调用函数Discretization，首先对数组进行去重操作并保存在a中，并构建函数getId用于获得元素值与对应序号之间的映射关系。

而后我们初始化数组c，用于储存数组a的前缀和。我们只需要从后向前遍历数组nums，就可以利用getId找到其在数组c中的对应序号。而后我们只需要计算此时c中对应位置左侧的前缀和即可获得当前数组中既在nums[i]右侧又小于nums[i]的元素。值得注意的是，此处为了加快运算，我们使用二进制中末尾为 1 的位置进行加速查找。而后我们根据当前的序号对应更新c中的前缀和。考虑到我们是向数组末尾添加元素，我们最终对数组进行逆序操作即可。

class Solution {
private:vector c;vector a;void Init(int length) {c.resize(length, 0);}int LowBit(int x) {return x & (-x);}void Update(int pos) {while (pos < c.size()) {c[pos] += 1;pos += LowBit(pos);}}int Query(int pos) {int ret = 0;while (pos > 0) {ret += c[pos];pos -= LowBit(pos);}return ret;}void Discretization(vector& nums) {a.assign(nums.begin(), nums.end());sort(a.begin(), a.end());a.erase(unique(a.begin(), a.end()), a.end());}int getId(int x) {return lower_bound(a.begin(), a.end(), x) - a.begin() + 1;}
public:vector countSmaller(vector& nums) {vector resultList;Discretization(nums);Init(nums.size() + 1);for (int i = (int)nums.size() - 1; i >= 0; --i) {int id = getId(nums[i]);resultList.push_back(Query(id - 1));Update(id);}reverse(resultList.begin(), resultList.end());return resultList;}
};

2、二分查找

同样参考LeetCode-剑指51-数组中的逆序对。我们可以在进行归并排序时，对于左区间中的每一个元素，统计右区间中元素小于它的个数并对应更新即可。其中函数inplace_merge可用于两个有序序列的升序排序。

class Solution {
public:using pii = pair; // vector countSmaller(vector& nums) {vector v;v.reserve(nums.size());for (int i = 0; i < nums.size(); ++i) {v.emplace_back(nums[i], i);}vector res(v.size());merge_sort(v, 0, v.size(), res);return res;}void merge_sort(vector& nums, int lo, int hi, vector& res) {if (hi - lo <= 1) return; // 元素个数 <= 1 终止。int mid = lo + (hi - lo >> 1);merge_sort(nums, lo, mid, res);merge_sort(nums, mid, hi, res);int right = mid;// 对于左半区间中的每个元素 left，统计右侧比它小的元素的个数for (int left = lo; left < mid; ++left) {while (right != hi && nums[left] > nums[right]) ++right;res[nums[left].second] += right - mid;}inplace_merge(nums.begin() + lo, nums.begin() + mid, nums.begin() + hi);}
};