315 计算右侧小于当前元素的个数（树状数组）_长方形内点的数量 树状数组

1. 问题描述：

给定一个整数数组 nums，按要求返回一个新数组 counts。数组 counts 有该性质： counts[i] 的值是  nums[i] 右侧小于 nums[i] 的元素的数量。

示例：

输入：nums = [5,2,6,1]
输出：[2,1,1,0] 

解释：

5 的右侧有 2 个更小的元素 (2 和 1)
2 的右侧仅有 1 个更小的元素 (1)
6 的右侧有 1 个更小的元素 (1)
1 的右侧有 0 个更小的元素提示：
0 <= nums.length <= 10 ^ 5
-10 ^ 4 <= nums[i] <= 10 ^ 4

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/count-of-smaller-numbers-after-self/

2. 思路分析：

这道题目其实有很多种的解决方法，这里使用树状数组的解法。其实想到树状数组的时候那么剩下来的就不难了（关键是需要想到这个），树状数组主要有两个功能：① 将数组中的某个位置加上一个值 ② 求解[1: x]区间的前缀和；对应的这道题目我们其实可以每遍历一个数字x，在树状数组tr中查找一下[1: x - 1]的个数即可，查找x之后那么将树状数组对应的当前位置加上一个1即可，例如题目中的[5,2,6,1]，我们可以逆序遍历列表，从1开始发现结果为0所以右侧小于1的个数为0，然后第二个数字6寻找一下tr[1:5]区间的个数，发现结果为1所以右侧小于6的个数为1，第三个数字为2找一下tr[1:2]的个数为1，发现结果为1所以右侧小于2的个数为1，同理5的右侧小于5的个数结果为2。在树状数组对应的nums[i]位置加上1即可，查找元素的时候在[1: x - 1]区间内查找元素个数即可。

3. 代码如下：

from typing import List
 
 
class Solution:
    tr = None
 
    # 返回最低位二进制的1对应的数字
    def lowbit(self, x: int):
        return x & -x
    
    # 查找[1:x]的前缀和
    def query(self, x: int):
        tr = self.tr
        i = x
        res = 0
        while i > 0:
            res += tr[i]
            i -= self.lowbit(i)
        return res
    
    # 在树状数组的x位置加上v
    def add(self, x: int, v: int):
        i = x
        tr = self.tr
        while i < len(tr):
            tr[i] += v
            i += self.lowbit(i)
 
    def countSmaller(self, nums: List[int]) -> List[int]:
        n = len(nums)
        # 这里以
        self.tr = [0] * 20002
        res = [0] * n
        for i in range(n - 1, -1, -1):
            # 因为nums有可能是负数最小为10000所以需要加上10001这样对应的树状数组最小的也从下标1开始, 其实是映射的关系(偏移量)
            res[i] = self.query(nums[i] + 10001 - 1)
            self.add(nums[i] + 10001, 1)
        return res