## Approach 1: Fenwick Tree

• Time:O(n\log n)
• Space:O(n)

## C++

``````class FenwickTree {
public:
FenwickTree(int n) : sums(n + 1) {}

void update(int i, int delta) {
while (i < sums.size()) {
sums[i] += delta;
i += lowbit(i);
}
}

int get(int i) const {
int sum = 0;
while (i > 0) {
sum += sums[i];
i -= lowbit(i);
}
return sum;
}

private:
vector<int> sums;

static inline int lowbit(int i) {
return i & -i;
}
};

class Solution {
public:
vector<int> countSmaller(vector<int>& nums) {
vector<int> ans(nums.size());
unordered_map<int, int> ranks;
getRanks(nums, ranks);
FenwickTree tree(ranks.size());

for (int i = nums.size() - 1; i >= 0; --i) {
const int num = nums[i];
ans[i] = tree.get(ranks[num] - 1);
tree.update(ranks[num], 1);
}

return ans;
}

private:
void getRanks(const vector<int>& nums, unordered_map<int, int>& ranks) {
set<int> sorted(begin(nums), end(nums));
int rank = 0;
for (const int num : sorted)
ranks[num] = ++rank;
}
};
``````

## JAVA

``````class FenwickTree {
public FenwickTree(int n) {
sums = new int[n + 1];
}

public void update(int i, int delta) {
while (i < sums.length) {
sums[i] += delta;
i += lowbit(i);
}
}

public int get(int i) {
int sum = 0;
while (i > 0) {
sum += sums[i];
i -= lowbit(i);
}
return sum;
}

private int[] sums;

private static int lowbit(int i) {
return i & -i;
}
}

class Solution {
public List<Integer> countSmaller(int[] nums) {
List<Integer> ans = new ArrayList<>();
Map<Integer, Integer> ranks = new HashMap<>();
getRanks(nums, ranks);
FenwickTree tree = new FenwickTree(ranks.size());

for (int i = nums.length - 1; i >= 0; --i) {
final int num = nums[i];
tree.update(ranks.get(num), 1);
}

Collections.reverse(ans);
return ans;
}

private void getRanks(int[] nums, Map<Integer, Integer> ranks) {
SortedSet<Integer> sorted = new TreeSet<>();
for (final int num : nums)
int rank = 0;
for (Iterator<Integer> it = sorted.iterator(); it.hasNext();)
ranks.put(it.next(), ++rank);
}
}
``````

## Python

``````class FenwickTree:
def __init__(self, n: int):
self.sums = [0] * (n + 1)

def update(self, i: int, delta: int) -> None:
while i < len(self.sums):
self.sums[i] += delta
i += self._lowbit(i)

def get(self, i: int) -> int:
sum = 0
while i > 0:
sum += self.sums[i]
i -= self._lowbit(i)
return sum

def _lowbit(self, i) -> int:
return i & -i

class Solution:
def countSmaller(self, nums: List[int]) -> List[int]:
ans = []
ranks = Counter()
self._getRanks(nums, ranks)
tree = FenwickTree(len(ranks))

for num in reversed(nums):
ans.append(tree.get(ranks[num] - 1))
tree.update(ranks[num], 1)

return ans[::-1]

def _getRanks(self, nums: List[int], ranks: Dict[int, int]) -> None:
rank = 0
for num in sorted(set(nums)):
rank += 1
ranks[num] = rank
``````

## Approach 2: Segment Tree

• Time:O(n\log n)
• Space:O(n)

## C++

``````struct SegmentTreeNode {
int lo;
int hi;
int sum;
SegmentTreeNode* left;
SegmentTreeNode* right;
SegmentTreeNode(int lo, int hi, int sum, SegmentTreeNode* left = nullptr,
SegmentTreeNode* right = nullptr)
: lo(lo), hi(hi), sum(sum), left(left), right(right) {}
~SegmentTreeNode() {
delete left;
delete right;
left = nullptr;
right = nullptr;
}
};

class SegmentTree {
public:
SegmentTree(const vector<int>& nums)
: root(build(nums, 0, nums.size() - 1)) {}

void update(int i, int val) {
update(root.get(), i, val);
}

int sumRange(int i, int j) const {
return sumRange(root.get(), i, j);
}

private:
std::unique_ptr<SegmentTreeNode> root;

SegmentTreeNode* build(const vector<int>& nums, int lo, int hi) const {
if (lo == hi)
return new SegmentTreeNode(lo, hi, nums[lo]);
const int mid = (lo + hi) / 2;
auto left = build(nums, lo, mid);
auto right = build(nums, mid + 1, hi);
return new SegmentTreeNode(lo, hi, left->sum + right->sum, left, right);
}

void update(SegmentTreeNode* root, int i, int val) {
if (root->lo == i && root->hi == i) {
root->sum += val;
return;
}
const int mid = (root->lo + root->hi) / 2;
if (i <= mid)
update(root->left, i, val);
else
update(root->right, i, val);
root->sum = root->left->sum + root->right->sum;
}

int sumRange(SegmentTreeNode* root, int i, int j) const {
if (root->lo == i && root->hi == j)
return root->sum;
const int mid = (root->lo + root->hi) / 2;
if (j <= mid)
return sumRange(root->left, i, j);
if (i > mid)
return sumRange(root->right, i, j);
return sumRange(root->left, i, mid) + sumRange(root->right, mid + 1, j);
}
};

class Solution {
public:
vector<int> countSmaller(vector<int>& nums) {
vector<int> ans(nums.size());
unordered_map<int, int> ranks;
getRanks(nums, ranks);
SegmentTree tree(vector<int>(ranks.size() + 1));

for (int i = nums.size() - 1; i >= 0; --i) {
const int num = nums[i];
ans[i] = tree.sumRange(0, ranks[num] - 1);
tree.update(ranks[num], 1);
}

return ans;
}

private:
void getRanks(const vector<int>& nums, unordered_map<int, int>& ranks) {
set<int> sorted(begin(nums), end(nums));
int rank = 0;
for (const int num : sorted)
ranks[num] = ++rank;
}
};
``````

## Approach 3: Merge Sort

• Time:O(n\log n)
• Space:O(n)

## C++

``````struct Item {
int num;
int index;
Item(int num = 0, int index = 0) : num(num), index(index) {}
};

class Solution {
public:
vector<int> countSmaller(vector<int>& nums) {
const int n = nums.size();
vector<int> ans(n);
vector<Item> items(n);

for (int i = 0; i < n; ++i)
items[i] = Item(nums[i], i);

mergeSort(items, 0, n - 1, ans);
return ans;
}

private:
void mergeSort(vector<Item>& items, int l, int r, vector<int>& ans) {
if (l >= r)
return;

const int m = (l + r) / 2;
mergeSort(items, l, m, ans);
mergeSort(items, m + 1, r, ans);
merge(items, l, m, r, ans);
}

void merge(vector<Item>& items, int l, int m, int r, vector<int>& ans) {
vector<Item> sorted(r - l + 1);
int k = 0;           // sorted's index
int i = l;           // left's index
int j = m + 1;       // right's index
int rightCount = 0;  // # of nums < items[i].num

while (i <= m && j <= r)
if (items[i].num > items[j].num) {
++rightCount;
sorted[k++] = items[j++];
} else {
ans[items[i].index] += rightCount;
sorted[k++] = items[i++];
}

// put possible remaining left part to the sorted array
while (i <= m) {
ans[items[i].index] += rightCount;
sorted[k++] = items[i++];
}

// put possible remaining right part to the sorted array
while (j <= r)
sorted[k++] = items[j++];

copy(begin(sorted), end(sorted), begin(items) + l);
}
};
``````

## JAVA

``````class Item {
public int num;
public int index;
public Item(int num, int index) {
this.num = num;
this.index = index;
}
}

class Solution {
public List<Integer> countSmaller(int[] nums) {
final int n = nums.length;
int[] ans = new int[n];
Item[] items = new Item[n];

for (int i = 0; i < n; ++i)
items[i] = new Item(nums[i], i);

mergeSort(items, 0, n - 1, ans);

return Arrays.stream(ans).boxed().collect(Collectors.toList());
}

private void mergeSort(Item[] items, int l, int r, int[] ans) {
if (l >= r)
return;

final int m = (l + r) / 2;
mergeSort(items, l, m, ans);
mergeSort(items, m + 1, r, ans);
merge(items, l, m, r, ans);
}

private void merge(Item[] items, int l, int m, int r, int[] ans) {
Item[] sorted = new Item[r - l + 1];
int k = 0;          // sorted's index
int i = l;          // left's index
int j = m + 1;      // right's index
int rightCount = 0; // # of nums < items[i].num

while (i <= m && j <= r)
if (items[i].num > items[j].num) {
++rightCount;
sorted[k++] = items[j++];
} else {
ans[items[i].index] += rightCount;
sorted[k++] = items[i++];
}

// put possible remaining left part to the sorted array
while (i <= m) {
ans[items[i].index] += rightCount;
sorted[k++] = items[i++];
}

// put possible remaining right part to the sorted array
while (j <= r)
sorted[k++] = items[j++];

System.arraycopy(sorted, 0, items, l, sorted.length);
}
}
``````

## Python

``````class Item:
def __init__(self, num: int = 0, index: int = 0):
self.num = num
self.index = index

class Solution:
def countSmaller(self, nums: List[int]) -> List[int]:
n = len(nums)
ans = [0] * n
items = [Item(num, i) for i, num in enumerate(nums)]

self._mergeSort(items, 0, n - 1, ans)
return ans

def _mergeSort(self, items: List[Item], l: int, r: int, ans: List[int]) -> None:
if l >= r:
return

m = (l + r) // 2
self._mergeSort(items, l, m, ans)
self._mergeSort(items, m + 1, r, ans)
self._merge(items, l, m, r, ans)

def _merge(self, items: List[Item], l: int, m: int, r: int, ans: List[int]) -> None:
sorted = [Item()] * (r - l + 1)
k = 0           # sorted's index
i = l           # left's index
j = m + 1       # right's index
rightCount = 0  # # of nums < items[i].num

while i <= m and j <= r:
if items[i].num > items[j].num:
rightCount += 1
sorted[k] = items[j]
k += 1
j += 1
else:
ans[items[i].index] += rightCount
sorted[k] = items[i]
k += 1
i += 1

# put possible remaining left part to the sorted array
while i <= m:
ans[items[i].index] += rightCount
sorted[k] = items[i]
k += 1
i += 1

# put possible remaining right part to the sorted array
while j <= r:
sorted[k] = items[j]
k += 1
j += 1

items[l:l + len(sorted)] = sorted
``````