Leetcode 315. Count of Smaller Numbers After Self

[Woodyiiiiiii]

这道题的解法是树状数组，或者也叫Binary indexed tree，或者是AKA Fenwick Tree。

树状数组的用处是求前缀和。我们普通的求数组前缀和，与修改数据，必有一个方法是O(n)时间复杂度，而树状数组平衡了两者，使两者的复杂度都在O(nlgn)。

具体原理可以看如下视频：B站五分钟丝滑动画讲解 | 树状数组

那么树状数组基于求前缀和的性质，我目前觉得有两种主要用处：

1. 单纯计算前缀和(+本身)
2. 计算前面比他大/小的数目(+1)

那么这道题就是第二个用处。首先构建数组，注意长度，索引为0的位置是不能用的，然后数组长度能包揽所有元素；其次，add方法记录次数+1，sum方法记录比当前位置小的元素出现次数的总和。

class Solution {
    public List<Integer> countSmaller(int[] nums) {
        int n = 10001;
        int[] b = new int[2 * n];
        List<Integer> ans = new ArrayList<>();
        for (int i = nums.length - 1; i >= 0; i--) {
            ans.add(sum(b, nums[i] + n - 1));
            add(b, nums[i] + n, 1);
        }
        Collections.reverse(ans);
        return ans;
    }

    // binary indexed tree
    public void add(int[] b, int i, int v) {
        while (i < b.length) {
            b[i] += v;
            i += i & -i;
        }
    }

    public int sum(int[] b, int i) {
        int s = 0;
        while (i > 0) {
            s += b[i];
            i -= i & -i;
        }
        return s;
    }
}

相同类型题目题目：

• 315. Count of Smaller Numbers After Self
• 327. Count of Range Sum
• 2179. Count Good Triplets in an Array

---

• 模版