[树状数组]leetcode315：计算右侧小于当前元素的个数(hard)

树状数组]leetcode315：计算右侧小于当前元素的个数(hard)"/>

[树状数组]leetcode315：计算右侧小于当前元素的个数(hard)

题目：

题解：

思路：树状数组

• 参考 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上增加数量1void 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]映射到位置kint k=a[i]+offset;// 统计位置k-1之前的元素个数res[i]=sum(k-1);// 每处理一个数，就把k加入到集合中去，相当于在k这个位置上+1add(k,1);}return res;}
};