LeetCode 315 计算右侧小于当前元素的个数（树状数组）_树状数组求数组中一个数右边比它小的数的个数

题目描述
给定一个整数数组 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 个更小的元素

树状数组视频链接
树状数组的作用：动态维护前缀和，前提是所有的数从1开始。树状数组tr[x] 保存的是以x为根节点的子树中叶节点的和。可以看下面的图，每一层末尾的零个数是相等的。tr[x]的长度为lowbit(x)，还可以看出tr[x]的父节点是t[x+lowbit(x)],树的深度是log₂n+1

基本操作lowbit(x)：指的是非负整数n在二进制表示下最低位1以及后面0所构成的数字。例如：x = 10010，lowbit(x)=(10)₂=2，lowbit(x)=x&(-x)
有两个操作：

• add(x,k)：为数字x加上k，由于树状数组是维护前缀和的，因此只要其中一个数字加上了k,那么后续的前缀数组也需要加k,但是在树状数组中只需要在 x, x+lowbit(x) …… 直到x < n 这几个位置上加上k即可。
  
• query(x)：查询x的前缀和，只需要将 x ，x-lowbit(x) …… 直到x>0 为止，这些位置的和相加就是x的前缀和。
  
  应用：
  单点修改以及区间查询；
  区间修改，单点查询；
  
  区间修改，区间查询。
  
  对于本题目：树状数组下标存储的是数值，数组里面存储的是个数。从后向前遍历数组，查询query(x-1)，也就是查询比x小的数的个数之和，然后修改树状数组x位置的值，因为x出现了一次，因此在x位置加1。注意由于数字的范围可能出现负数，不符合树状数组应用的条件，因此需要将每个数变成>=1的，在每一个数上加一个大的正数即可。

class Solution {
public:
    int n=20001;
    vector<int> tr;
    int lowbit(int x)
    {
        return x & -x;
    }
    void add(int x,int k)
    {       
        for(int i=x;i<=n;i+=lowbit(i)) tr[i]+=k;      
    }
    int query(int x)
    {
        int res=0;
        for(int i=x;i;i-=lowbit(i)) res+=tr[i];
        return res;
    }
    vector<int> countSmaller(vector<int>& nums) {
        tr.resize(n+1);
        vector<int> res(nums.size());
        for(int i=nums.size()-1;i>=0;i--)
        {
            int x=nums[i]+10001;
            res[i]=query(x-1);
            add(x,1);
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30