[树状数组]leetcode315：计算右侧小于当前元素的个数(hard)_树状数组位置i左(右)边小于a[i]的个数

题目：

题解：

思路：树状数组

• 参考 acw 上的 241. 楼兰图腾，从右至左扫描数组，由于数组元素可能为负数，因此加上一个偏移量通通表示为正数，然后计算位置 k 之前元素个数即为 a[i] 右边小于 a[i] 的元素个数，计算结束则将该位置 k 加入集合，即在位置 k 上1。

代码如下：

const int offset = 1e4+1,N = 2e4+10;
class Solution {
private:
    int tree[N];
    // 以下为树状数组三个函数的默写
    int lowbit(int x){
        return x&-x;
    }
    // 在位置x上增加数量1
    void add(int x,int v){
        for(int i=x;i<=N;i+=lowbit(i))
            tree[i]+=v;
    }

    // 统计小于等于x的元素个数
    int sum(int x){
        int res=0;
        for(int i=x;i;i-=lowbit(i))
            res+=tree[i];
        return res;
    }

public:
    vector<int> countSmaller(vector<int>& a) {
        int n=a.size();
        vector<int> res(n,0);
        memset(tree,0,sizeof tree);
        // 从右向左扫描，统计每个数右边比它小的数的个数
        for(int i=n-1;i>=0;i--){
            // 偏移量是为了处理负数的，将a[i]映射到位置k
            int k=a[i]+offset;
            // 统计位置k-1之前的元素个数
            res[i]=sum(k-1);
            // 每处理一个数，就把k加入到集合中去，相当于在k这个位置上+1
            add(k,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
31
32
33
34
35
36
37
38
39