企业官网建设流程全解析

1. 这道题到底在考什么

LeetCode 315 题，计算右侧小于当前元素的个数。题目描述很简洁：给你一个整数数组 nums，要求返回一个新数组 counts，其中 counts[i] 表示 nums[i] 右侧所有元素中比 nums[i] 小的元素个数。举个例子，nums = [5,2,6,1]，返回 [2,1,1,0]。5 右边有 2 和 1 比它小，所以是 2；2 右边只有 1 比它小，所以是 1；6 右边只有 1 比它小，所以是 1；1 右边没有元素，所以是 0。

这道题在 LeetCode 上的标签是「树状数组」「线段树」「归并排序」「二分查找」，难度标注为困难。很多人第一次看到这道题，第一反应是暴力双重循环，时间复杂度 O(n²)，n 等于数组长度。如果数组长度只有几千，暴力完全没问题，但题目给定的数组长度可以达到 10⁵ 级别，暴力解法直接超时。所以这道题的核心考点就是：如何把 O(n²) 的暴力枚举优化到 O(n log n)。

我个人的经验是，这道题是学习「归并排序求逆序对」和「树状数组」这两个经典技巧的绝佳入口。它不像有些困难题那样需要复杂的思维跳跃，而是非常直接地考察你对这两种数据结构的理解和应用能力。你只要掌握了其中任意一种方法，就能稳稳地通过。而且这道题的解法具有很强的迁移性，学会了之后，类似「统计逆序对」「区间计数」的问题都能用同样的思路去解决。

这篇文章我会从两种主流解法入手，把归并排序和树状数组的实现细节、核心原理、代码模板、常见坑点全部拆开讲清楚。无论你是刚接触算法竞赛的新手，还是正在准备面试的开发者，都能从中找到可以直接复用的代码和思路。我还会对比两种方法的优劣，给出在不同场景下的选择建议，以及我在实际刷题和面试中总结出来的一些实用技巧。

2. 为什么暴力解法不够用

2.1 暴力解法的直观逻辑与复杂度瓶颈

暴力解法的思路非常直接：对于数组中的每一个位置 i，遍历它右边所有的元素 j（j > i），如果 nums[j] < nums[i]，就把计数器加一。用代码写出来大概是这样：

def countSmaller(nums): n = len(nums) counts = [0] * n for i in range(n): for j in range(i + 1, n): if nums[j] < nums[i]: counts[i] += 1 return counts

这段代码逻辑上完全正确，没有任何问题。但它的时间复杂度是 O(n²)。当 n = 10⁵ 时，n² = 10¹⁰，也就是一百亿次操作。即使每次操作只需要一个 CPU 周期，现代处理器每秒能执行大约 10⁹ 次操作，那也需要十秒钟以上。而 LeetCode 的时间限制通常是 1 到 2 秒，所以暴力解法必然超时。

这里有一个很多人容易忽略的点：暴力解法的时间复杂度不仅取决于 n，还取决于数据的分布。如果数组是严格递增的，那么对于每个 i，右边没有任何元素比它小，内层循环虽然还是会执行，但 if 条件永远不成立。不过时间复杂度仍然是 O(n²)，因为循环本身的开销还在。所以不要指望通过数据特性来「侥幸」通过。

2.2 从 O(n²) 到 O(n log n) 的优化思路

要把 O(n²) 降到 O(n log n)，核心思路就是减少重复比较。在暴力解法中，对于每个 i，我们都在重新扫描它右边的所有元素，做了大量重复的工作。如果我们能在扫描的过程中，顺便把元素之间的大小关系「记录」下来，后续就不需要再重新比较了。

这就引出了两种经典的优化方向：

第一种是归并排序。归并排序在合并两个有序子数组的过程中，天然地可以统计出「右边有多少个元素比左边小」这个信息。因为归并排序的合并过程本身就是按大小顺序进行的，当我们在合并时发现右边的某个元素比左边的元素小，就可以直接计算出贡献。归并排序的时间复杂度是 O(n log n)，在排序的同时顺便完成统计，非常优雅。

第二种是树状数组（也叫二叉索引树，Binary Indexed Tree）。树状数组擅长处理「单点更新、前缀查询」的问题。我们可以从右往左遍历数组，每遇到一个元素，就查询当前树状数组中比它小的元素个数，然后再把它插入树状数组。这样每个元素的查询和插入都是 O(log n)，总共 n 个元素，总时间复杂度 O(n log n)。

这两种方法各有优劣，下面我会分别详细展开。

3. 归并排序解法：在排序中顺便统计

3.1 归并排序统计逆序对的核心原理

归并排序的基本思想是分治法：把数组分成两半，分别排序，然后把两个有序数组合并成一个有序数组。在合并的过程中，我们可以顺便统计出「右侧小于当前元素的个数」。

具体来说，假设我们有两个已经排好序的子数组 left 和 right，现在要把它们合并。我们用两个指针 i 和 j 分别指向 left 和 right 的开头。当 left[i] <= right[j] 时，我们把 left[i] 放入合并后的数组，此时 right 中从 j 开始到末尾的所有元素都比 left[i] 大（因为 right 是有序的），所以 left[i] 右侧比它小的元素个数就是 j 的值。当 left[i] > right[j] 时，我们把 right[j] 放入合并后的数组，j 向后移动。

这个过程中，关键点在于：当我们将 left[i] 放入结果数组时，right 中已经被放入结果数组的元素个数（也就是 j 的值），就是 left[i] 右侧比它小的元素个数。因为 right 中已经被放入的元素都是比 left[i] 小的，而它们原本在原始数组中位于 left[i] 的右侧。

但这里有一个容易出错的地方：归并排序会改变元素的原始位置。我们需要在排序的过程中，同时记录每个元素的原始索引，这样才能把统计结果放到正确的位置上。所以我们需要一个索引数组，跟随元素一起排序。

3.2 带索引的归并排序实现细节

下面是我常用的归并排序解法模板，用 Python 实现：

def countSmaller(nums): n = len(nums) counts = [0] * n # 索引数组，记录每个元素的原始位置 indices = list(range(n)) def merge_sort(start, end): if end - start <= 1: return mid = (start + end) // 2 merge_sort(start, mid) merge_sort(mid, end) # 合并两个有序子数组 temp = [] i, j = start, mid while i < mid and j < end: if nums[indices[i]] <= nums[indices[j]]: # 右侧比 indices[i] 小的元素个数就是 j - mid counts[indices[i]] += j - mid temp.append(indices[i]) i += 1 else: temp.append(indices[j]) j += 1 while i < mid: counts[indices[i]] += j - mid temp.append(indices[i]) i += 1 while j < end: temp.append(indices[j]) j += 1 indices[start:end] = temp merge_sort(0, n) return counts

这段代码的核心在于counts[indices[i]] += j - mid这一行。当我们将左侧元素indices[i]放入结果数组时，右侧子数组中已经被放入结果数组的元素个数是j - mid，这些元素都比nums[indices[i]]小，而且它们在原始数组中都位于indices[i]的右侧。所以j - mid就是我们要累加的值。

有一个细节需要注意：当nums[indices[i]] == nums[indices[j]]时，我们选择先放入左侧元素。这是因为题目要求的是「小于」而不是「小于等于」，如果先放入右侧元素，那么相等的元素会被错误地计入。所以判断条件必须是<=而不是<。

3.3 归并排序解法的复杂度分析与注意事项

归并排序解法的时间复杂度是 O(n log n)，空间复杂度是 O(n)。空间主要消耗在索引数组和临时数组上。这个复杂度对于 n = 10⁵ 的数据规模来说完全够用，实际运行时间通常在几百毫秒以内。

在实际写代码的时候，有几个坑我踩过好几次，这里分享出来：

第一个坑是递归深度。Python 的默认递归深度限制是 1000，当 n = 10⁵ 时，归并排序的递归深度大约是 log₂(10⁵) ≈ 17，远远小于 1000，所以不会有问题。但如果你用其他语言或者递归实现不当，可能会遇到栈溢出的问题。

第二个坑是索引数组的更新。在合并完成后，必须把临时数组的内容写回indices[start:end]，而不是写回nums。因为nums的原始顺序不能改变，我们只是通过indices来间接排序。如果直接修改nums，后续的统计就会出错。

第三个坑是边界条件。当end - start <= 1时直接返回，这是递归的终止条件。如果写成end - start == 0，当子数组只有一个元素时不会返回，会导致无限递归。这个细节虽然小，但很容易写错。

提示：归并排序解法的一个额外好处是，它不依赖于元素的值域。即使数组中的元素是负数、浮点数或者很大的整数，归并排序都能正确处理。而树状数组解法通常需要先做离散化，这一点后面会详细讲。

4. 树状数组解法：从右往左的巧妙统计

4.1 树状数组的基本原理与适用场景

树状数组（Binary Indexed Tree，简称 BIT）是一种支持「单点更新」和「前缀查询」的数据结构，两种操作的时间复杂度都是 O(log n)。它的核心思想是利用二进制的特性，把数组分成若干个区间，每个区间维护一个和值。

树状数组的经典应用场景包括：统计逆序对、求区间和、求第 k 小元素等。对于这道题，我们需要的是：从右往左遍历数组，对于每个元素，查询当前已经插入的元素中有多少个比它小，然后把它插入树状数组。

树状数组的实现非常简洁，核心就是两个函数：update(i, delta)和query(i)。update用于在位置 i 上增加 delta，query用于查询前缀 [1, i] 的和。代码模板如下：

class BIT: def __init__(self, n): self.n = n self.tree = [0] * (n + 1) def update(self, i, delta): while i <= self.n: self.tree[i] += delta i += i & (-i) def query(self, i): s = 0 while i > 0: s += self.tree[i] i -= i & (-i) return s

这段代码看起来很简单，但i & (-i)这个操作是树状数组的精髓。它利用了补码的性质，取出 i 的二进制表示中最低位的 1 所对应的值。比如 i = 6（二进制 110），i & (-i)= 2（二进制 010）。这个操作决定了树状数组中每个节点覆盖的区间范围。

4.2 离散化处理：把大值域映射到小范围

树状数组的索引必须是正整数，而且通常不能太大。但题目中的 nums 元素可能是负数、零或者很大的整数，值域可能达到 10⁹ 甚至更大。所以我们需要先对数组进行离散化：把原始值映射到 1 到 m 的排名，其中 m 是不同值的个数。

离散化的步骤如下：

1. 把 nums 中的所有元素去重，然后排序。
2. 对于每个元素，用二分查找找到它在排序后数组中的位置（从 1 开始计数）。
3. 用这个位置作为树状数组的索引。

举个例子，nums = [5, 2, 6, 1]，去重排序后得到 [1, 2, 5, 6]。5 的排名是 3，2 的排名是 2，6 的排名是 4，1 的排名是 1。所以离散化后的数组是 [3, 2, 4, 1]。

离散化的代码实现：

def discretize(nums): sorted_unique = sorted(set(nums)) rank = {v: i + 1 for i, v in enumerate(sorted_unique)} return [rank[v] for v in nums]

这里用字典来做映射，查询时间是 O(1)，比二分查找的 O(log n) 更快。但字典会消耗额外的空间，如果内存紧张，可以用二分查找代替。

4.3 从右往左遍历的完整实现与参数计算

离散化完成后，我们就可以从右往左遍历数组，用树状数组来统计了。完整代码如下：

def countSmaller(nums): if not nums: return [] n = len(nums) # 离散化 sorted_unique = sorted(set(nums)) rank = {v: i + 1 for i, v in enumerate(sorted_unique)} m = len(sorted_unique) bit = BIT(m) counts = [0] * n # 从右往左遍历 for i in range(n - 1, -1, -1): r = rank[nums[i]] # 查询比当前元素小的元素个数 counts[i] = bit.query(r - 1) # 把当前元素插入树状数组 bit.update(r, 1) return counts

这段代码的核心逻辑是：对于位置 i 的元素，bit.query(r - 1)查询的是树状数组中排名小于 r 的元素个数，也就是值比 nums[i] 小的元素个数。由于我们是从右往左遍历的，树状数组中已经插入的元素都是 nums[i] 右侧的元素，所以查询结果正好就是「右侧小于当前元素的个数」。

这里有一个细节需要注意：查询的是r - 1而不是r。因为我们要统计的是严格小于当前元素的个数，如果查询r，会把等于当前元素的元素也计入。所以必须用r - 1。

4.4 树状数组解法的复杂度与边界情况

树状数组解法的时间复杂度是 O(n log n)，其中离散化需要 O(n log n)，遍历需要 O(n log n)。空间复杂度是 O(n)，主要用于存储树状数组和离散化后的排名。

边界情况方面，有几个地方需要特别注意：

第一，空数组。如果 nums 为空，直接返回空数组。虽然题目通常不会给空数组，但防御性编程是好习惯。

第二，所有元素相同。如果 nums = [1, 1, 1]，离散化后所有元素的排名都是 1。从右往左遍历时，每次查询query(0)都返回 0，所以 counts = [0, 0, 0]。这是正确的，因为没有任何元素严格小于另一个元素。

第三，元素值域很大。比如 nums = [1000000000, -1000000000]，离散化后排名是 [2, 1]，树状数组的大小只需要 2，完全没问题。这就是离散化的好处：把大值域压缩到小范围。

注意：树状数组的索引必须从 1 开始，不能从 0 开始。因为i & (-i)在 i = 0 时会陷入死循环。所以离散化后的排名必须从 1 开始，而不是从 0 开始。这个坑我在第一次写树状数组的时候踩过，调试了半天才发现问题。

5. 两种解法的对比与选择建议

5.1 时间复杂度与空间复杂度对比

从表格可以看出，两种解法在复杂度上几乎持平。归并排序不需要离散化，但代码稍微复杂一些；树状数组需要离散化，但核心逻辑更简洁。

5.2 不同场景下的选择建议

在实际刷题和面试中，我通常会根据以下场景来选择：

如果是面试场景，我倾向于选择归并排序。原因是归并排序的思路更直观，面试官更容易理解你的解题逻辑。而且归并排序不需要额外的离散化步骤，代码虽然长一点，但每一步都很清晰。面试官看到你写出带索引的归并排序，会认为你对分治算法有深入理解。

如果是竞赛场景，我倾向于选择树状数组。原因是树状数组的代码更短，写起来更快，而且不容易出错。在竞赛中，时间就是分数，能快速写出正确的代码比什么都重要。而且树状数组的模板非常固定，背下来之后可以直接套用。

如果是工程场景，需要根据具体需求来定。如果数据量不大，暴力解法就够了；如果数据量很大，两种方法都可以，但树状数组的内存占用通常更小，因为它的树状数组大小等于不同值的个数，而不是数组长度。

5.3 扩展思考：线段树与其他解法

除了归并排序和树状数组，这道题还可以用线段树来解决。线段树的思路和树状数组类似，也是从右往左遍历，查询区间内已插入元素的个数。但线段树的代码量比树状数组大得多，对于这道题来说有点「杀鸡用牛刀」的感觉。

还有一种解法是二分查找 + 有序数组。从右往左遍历，维护一个有序数组，对于每个元素，用二分查找找到它应该插入的位置，这个位置就是右侧比它小的元素个数。但插入操作需要 O(n) 的时间（因为要移动元素），所以总时间复杂度是 O(n²)，并不比暴力解法好。

所以综合来看，归并排序和树状数组是这道题的最优解。选择哪一种，主要看个人习惯和具体场景。

6. 常见问题与排查技巧实录

6.1 归并排序常见错误与排查

问题一：统计结果偏大或偏小。

这通常是因为在合并时，判断条件写成了<而不是<=。当左右两侧元素相等时，如果先放入右侧元素，那么相等的元素会被错误地计入「小于」的统计中。正确的做法是先放入左侧元素，确保相等元素不被计入。

问题二：索引数组没有正确更新。

在合并完成后，必须把临时数组的内容写回indices[start:end]。如果忘记写回，或者写回了nums，后续的统计就会出错。这个错误比较隐蔽，因为程序不会报错，只是结果不对。

问题三：递归终止条件写错。

递归的终止条件应该是end - start <= 1，而不是end - start == 0。如果写成== 0，当子数组只有一个元素时不会返回，会导致无限递归，最终栈溢出。

6.2 树状数组常见错误与排查

问题一：离散化排名从 0 开始。

树状数组的索引必须从 1 开始，如果离散化后的排名从 0 开始，update(0, 1)会陷入死循环。正确的做法是在离散化时把排名加 1。

问题二：查询时用了query(r)而不是query(r - 1)。

题目要求的是严格小于，如果查询query(r)，会把等于当前元素的元素也计入。所以必须用query(r - 1)。

问题三：树状数组大小开小了。

树状数组的大小应该等于不同值的个数，而不是数组长度。如果开小了，update时可能会越界。建议在初始化时用len(sorted_unique)作为大小。

6.3 通用调试技巧与性能优化建议

调试技巧一：用小规模数据手动验证。

对于归并排序，可以用 nums = [5, 2, 6, 1] 手动模拟合并过程，检查每一步的统计是否正确。对于树状数组，可以用 nums = [1, 2, 3, 4] 和 nums = [4, 3, 2, 1] 来验证。

调试技巧二：打印中间结果。

在归并排序中，可以在每次合并后打印indices和counts，观察是否符合预期。在树状数组中，可以在每次查询和更新后打印树状数组的内容。

性能优化建议一：使用迭代代替递归。

归并排序的递归实现虽然简洁，但递归调用有额外的开销。如果追求极致性能，可以用迭代版本的归并排序，但代码会复杂一些。

性能优化建议二：用数组代替字典做离散化。

字典的查询虽然是 O(1)，但常数因子比数组大。如果值域不大，可以直接用数组做映射。如果值域很大，可以用二分查找代替字典。

性能优化建议三：提前返回。

如果数组已经有序（递增），那么所有元素的 counts 都是 0，可以直接返回。这个优化虽然不能改变最坏时间复杂度，但在特定数据下可以大幅提速。

7. 我在实际刷题中的几点体会

这道题我前前后后做了大概五六遍，每次都有新的收获。第一次做的时候，我用了暴力解法，结果超时，然后看了题解才知道有归并排序和树状数组这两种方法。第二次做的时候，我照着题解写了归并排序，但因为没有处理好相等元素的情况，结果错了。第三次做的时候，我尝试自己写树状数组，结果因为离散化排名从 0 开始，陷入了死循环。

踩了这些坑之后，我总结出一个经验：对于这种经典题目，不要急着写代码，先把思路理清楚，把边界情况想明白，然后再动手。特别是树状数组，模板虽然固定，但细节很多，稍不注意就会出错。

另外，我建议大家在刷题的时候，不要只满足于「通过」，而是要尝试用多种方法解决同一道题。比如这道题，你可以先用归并排序做一遍，再用树状数组做一遍，然后对比两种方法的优劣。这样不仅能加深对算法的理解，还能在面试中展现出更全面的能力。

最后分享一个小技巧：如果你在面试中遇到了这道题，可以先说出暴力解法，然后分析它的复杂度瓶颈，再引出归并排序或树状数组的优化思路。这样即使你最后没有写完代码，面试官也能看到你的思考过程，这比直接写代码更重要。