給定整數陣列
nums，回傳陣列counts，其中counts[i]=nums[i]右側比它小的元素個數。
Example:
Input: nums = [5,2,6,1] Output: [2,1,1,0] （5 右側有 {2,1} 兩個更小；2 右側 {1}；6 右側 {1}；1 右側無）
Intuition
TIP
核心思路：這是「計算逆序對」的變形。用歸併排序，在合併兩段時，當左段元素被放入結果，就累加「此刻已從右段放入的元素數」——那些都是比它小且在它右邊的。
- 排序會打亂位置，所以追蹤每個值的原始索引，把計數記在
counts[原始索引] - 合併時右段元素先放（較小者），記下已放入的右段數量
rightCount - 左段元素放入時，
counts[該元素] += rightCount - 也可用樹狀數組（BIT）離線統計，或有序結構二分插入
Approaches
⭐ Merge Sort Counting — O(n log n) / O(n)
- Idea: 在 merge 階段，左段元素放入時累加已放入的右段數
- Time:
O(n log n)- 歸併 - Space:
O(n)- 索引與暫存
class Solution {
fun countSmaller(nums: IntArray): List<Int> {
val n = nums.size
val counts = IntArray(n)
val indices = IntArray(n) { it } // 追蹤原始索引
mergeSort(nums, indices, counts, 0, n - 1)
return counts.toList()
}
private fun mergeSort(nums: IntArray, idx: IntArray, counts: IntArray, lo: Int, hi: Int) {
if (lo >= hi) return
val mid = (lo + hi) ushr 1
mergeSort(nums, idx, counts, lo, mid)
mergeSort(nums, idx, counts, mid + 1, hi)
val merged = IntArray(hi - lo + 1)
var i = lo; var j = mid + 1; var k = 0
var rightCount = 0
while (i <= mid && j <= hi) {
if (nums[idx[j]] < nums[idx[i]]) {
rightCount++ // 右段這個更小者先放
merged[k++] = idx[j++]
} else {
counts[idx[i]] += rightCount // 左段元素：右邊已放的都更小
merged[k++] = idx[i++]
}
}
while (i <= mid) { counts[idx[i]] += rightCount; merged[k++] = idx[i++] }
while (j <= hi) merged[k++] = idx[j++]
for (t in merged.indices) idx[lo + t] = merged[t]
}
}Note: Fenwick Tree (BIT) Approach
把數值離散化（座標壓縮）後，從右往左掃描：對每個 nums[i]，查詢 BIT 中「比它小的值」的累計出現次數（即右側更小數），再把 nums[i] 加入 BIT。同樣 O(n log n)，但常數較小、也較容易擴充成各種區間統計。
🔑 Takeaways
- Pattern: 逆序對統計——歸併排序在 merge 階段順手計數，或用 BIT 離線統計
- Key trick: 排序會打亂位置，務必追蹤原始索引把計數寫回正確位置；歸併版的精髓是「左段元素放入時，右段已放入的都更小且在右邊」