LeetCode 315: Count of Smaller Numbers After Self (Coordinate Compression + Fenwick Tree)
LeetCode 315Fenwick TreeCoordinate CompressionToday we solve LeetCode 315 - Count of Smaller Numbers After Self.
Source: https://leetcode.com/problems/count-of-smaller-numbers-after-self/
English
Problem Summary
Given an integer array nums, return an array counts where counts[i] is the number of smaller elements to the right of nums[i].
Key Insight
Scan from right to left. If we can quickly know how many processed values are strictly smaller than current value, we can fill the answer in one pass. Fenwick Tree supports prefix-count query and point update in O(log n).
Algorithm
- Coordinate-compress values to ranks 1..m.
- Traverse nums from right to left.
- Query Fenwick prefix sum at rank - 1 to get smaller count.
- Update Fenwick at rank by +1.
- Reverse-free because we write directly to answer index.
Complexity Analysis
Time: O(n log n).
Space: O(n).
Common Pitfalls
- Forgetting coordinate compression for negative/large values.
- Querying rank instead of rank - 1, which includes equals.
- Using 0-based Fenwick indices by mistake.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
static class Fenwick {
int[] bit;
Fenwick(int n) { bit = new int[n + 1]; }
void add(int i, int delta) {
while (i < bit.length) {
bit[i] += delta;
i += i & -i;
}
}
int sum(int i) {
int s = 0;
while (i > 0) {
s += bit[i];
i -= i & -i;
}
return s;
}
}
public List<Integer> countSmaller(int[] nums) {
int n = nums.length;
int[] sorted = nums.clone();
Arrays.sort(sorted);
Map<Integer, Integer> rank = new HashMap<>();
int r = 1;
for (int x : sorted) {
if (!rank.containsKey(x)) rank.put(x, r++);
}
Fenwick fw = new Fenwick(rank.size());
Integer[] ans = new Integer[n];
for (int i = n - 1; i >= 0; i--) {
int k = rank.get(nums[i]);
ans[i] = fw.sum(k - 1);
fw.add(k, 1);
}
return Arrays.asList(ans);
}
}type Fenwick struct {
bit []int
}
func NewFenwick(n int) *Fenwick {
return &Fenwick{bit: make([]int, n+1)}
}
func (f *Fenwick) Add(i, delta int) {
for i < len(f.bit) {
f.bit[i] += delta
i += i & -i
}
}
func (f *Fenwick) Sum(i int) int {
s := 0
for i > 0 {
s += f.bit[i]
i -= i & -i
}
return s
}
func countSmaller(nums []int) []int {
n := len(nums)
sorted := append([]int(nil), nums...)
sort.Ints(sorted)
rank := map[int]int{}
r := 1
for _, x := range sorted {
if _, ok := rank[x]; !ok {
rank[x] = r
r++
}
}
fw := NewFenwick(len(rank))
ans := make([]int, n)
for i := n - 1; i >= 0; i-- {
k := rank[nums[i]]
ans[i] = fw.Sum(k - 1)
fw.Add(k, 1)
}
return ans
}class Fenwick {
public:
vector<int> bit;
Fenwick(int n) : bit(n + 1, 0) {}
void add(int i, int delta) {
for (; i < (int)bit.size(); i += i & -i) bit[i] += delta;
}
int sum(int i) {
int s = 0;
for (; i > 0; i -= i & -i) s += bit[i];
return s;
}
};
class Solution {
public:
vector<int> countSmaller(vector<int>& nums) {
vector<int> sorted = nums;
sort(sorted.begin(), sorted.end());
sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());
Fenwick fw((int)sorted.size());
int n = nums.size();
vector<int> ans(n);
for (int i = n - 1; i >= 0; --i) {
int k = lower_bound(sorted.begin(), sorted.end(), nums[i]) - sorted.begin() + 1;
ans[i] = fw.sum(k - 1);
fw.add(k, 1);
}
return ans;
}
};class Fenwick:
def __init__(self, n: int):
self.bit = [0] * (n + 1)
def add(self, i: int, delta: int) -> None:
while i < len(self.bit):
self.bit[i] += delta
i += i & -i
def sum(self, i: int) -> int:
s = 0
while i > 0:
s += self.bit[i]
i -= i & -i
return s
class Solution:
def countSmaller(self, nums: List[int]) -> List[int]:
vals = sorted(set(nums))
rank = {v: i + 1 for i, v in enumerate(vals)}
fw = Fenwick(len(vals))
ans = [0] * len(nums)
for i in range(len(nums) - 1, -1, -1):
k = rank[nums[i]]
ans[i] = fw.sum(k - 1)
fw.add(k, 1)
return ansclass Fenwick {
constructor(n) {
this.bit = new Array(n + 1).fill(0);
}
add(i, delta) {
while (i < this.bit.length) {
this.bit[i] += delta;
i += i & -i;
}
}
sum(i) {
let s = 0;
while (i > 0) {
s += this.bit[i];
i -= i & -i;
}
return s;
}
}
var countSmaller = function(nums) {
const vals = [...new Set(nums)].sort((a, b) => a - b);
const rank = new Map();
vals.forEach((v, i) => rank.set(v, i + 1));
const fw = new Fenwick(vals.length);
const ans = new Array(nums.length).fill(0);
for (let i = nums.length - 1; i >= 0; i--) {
const k = rank.get(nums[i]);
ans[i] = fw.sum(k - 1);
fw.add(k, 1);
}
return ans;
};中文
题目概述
给定整数数组 nums，返回数组 counts，其中 counts[i] 表示 nums[i] 右侧严格小于它的元素个数。
核心思路
从右往左扫描。每处理一个值，就把它加入数据结构；接着查询当前值有多少“更小值”已经出现。Fenwick 树可以高效支持前缀频次查询与单点更新。
算法步骤
- 先做坐标压缩，把值映射到 1..m。
- 从右到左遍历数组。
- 查询 rank - 1 的前缀和，得到右侧更小元素数。
- 在 rank 位置执行 +1 更新。
- 直接写入答案下标，无需额外反转。
复杂度分析
时间复杂度：O(n log n)。
空间复杂度：O(n)。
常见陷阱
- 忘记做坐标压缩，导致下标不可用。
- 误查 rank 而非 rank - 1，把相等元素也算进去了。
- Fenwick 树下标从 1 开始，0 下标会出错。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
static class Fenwick {
int[] bit;
Fenwick(int n) { bit = new int[n + 1]; }
void add(int i, int delta) {
while (i < bit.length) {
bit[i] += delta;
i += i & -i;
}
}
int sum(int i) {
int s = 0;
while (i > 0) {
s += bit[i];
i -= i & -i;
}
return s;
}
}
public List<Integer> countSmaller(int[] nums) {
int n = nums.length;
int[] sorted = nums.clone();
Arrays.sort(sorted);
Map<Integer, Integer> rank = new HashMap<>();
int r = 1;
for (int x : sorted) {
if (!rank.containsKey(x)) rank.put(x, r++);
}
Fenwick fw = new Fenwick(rank.size());
Integer[] ans = new Integer[n];
for (int i = n - 1; i >= 0; i--) {
int k = rank.get(nums[i]);
ans[i] = fw.sum(k - 1);
fw.add(k, 1);
}
return Arrays.asList(ans);
}
}type Fenwick struct {
bit []int
}
func NewFenwick(n int) *Fenwick {
return &Fenwick{bit: make([]int, n+1)}
}
func (f *Fenwick) Add(i, delta int) {
for i < len(f.bit) {
f.bit[i] += delta
i += i & -i
}
}
func (f *Fenwick) Sum(i int) int {
s := 0
for i > 0 {
s += f.bit[i]
i -= i & -i
}
return s
}
func countSmaller(nums []int) []int {
n := len(nums)
sorted := append([]int(nil), nums...)
sort.Ints(sorted)
rank := map[int]int{}
r := 1
for _, x := range sorted {
if _, ok := rank[x]; !ok {
rank[x] = r
r++
}
}
fw := NewFenwick(len(rank))
ans := make([]int, n)
for i := n - 1; i >= 0; i-- {
k := rank[nums[i]]
ans[i] = fw.Sum(k - 1)
fw.Add(k, 1)
}
return ans
}class Fenwick {
public:
vector<int> bit;
Fenwick(int n) : bit(n + 1, 0) {}
void add(int i, int delta) {
for (; i < (int)bit.size(); i += i & -i) bit[i] += delta;
}
int sum(int i) {
int s = 0;
for (; i > 0; i -= i & -i) s += bit[i];
return s;
}
};
class Solution {
public:
vector<int> countSmaller(vector<int>& nums) {
vector<int> sorted = nums;
sort(sorted.begin(), sorted.end());
sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());
Fenwick fw((int)sorted.size());
int n = nums.size();
vector<int> ans(n);
for (int i = n - 1; i >= 0; --i) {
int k = lower_bound(sorted.begin(), sorted.end(), nums[i]) - sorted.begin() + 1;
ans[i] = fw.sum(k - 1);
fw.add(k, 1);
}
return ans;
}
};class Fenwick:
def __init__(self, n: int):
self.bit = [0] * (n + 1)
def add(self, i: int, delta: int) -> None:
while i < len(self.bit):
self.bit[i] += delta
i += i & -i
def sum(self, i: int) -> int:
s = 0
while i > 0:
s += self.bit[i]
i -= i & -i
return s
class Solution:
def countSmaller(self, nums: List[int]) -> List[int]:
vals = sorted(set(nums))
rank = {v: i + 1 for i, v in enumerate(vals)}
fw = Fenwick(len(vals))
ans = [0] * len(nums)
for i in range(len(nums) - 1, -1, -1):
k = rank[nums[i]]
ans[i] = fw.sum(k - 1)
fw.add(k, 1)
return ansclass Fenwick {
constructor(n) {
this.bit = new Array(n + 1).fill(0);
}
add(i, delta) {
while (i < this.bit.length) {
this.bit[i] += delta;
i += i & -i;
}
}
sum(i) {
let s = 0;
while (i > 0) {
s += this.bit[i];
i -= i & -i;
}
return s;
}
}
var countSmaller = function(nums) {
const vals = [...new Set(nums)].sort((a, b) => a - b);
const rank = new Map();
vals.forEach((v, i) => rank.set(v, i + 1));
const fw = new Fenwick(vals.length);
const ans = new Array(nums.length).fill(0);
for (let i = nums.length - 1; i >= 0; i--) {
const k = rank.get(nums[i]);
ans[i] = fw.sum(k - 1);
fw.add(k, 1);
}
return ans;
};
Comments