LeetCode 315. Count of Smaller Numbers After Self(线段树，树状数组)

• 2020 年 3 月 17 日
• 筆記

题目

题意：找到数组里每个元素的右边有多少个元素小于当前元素

题解：单点更新，区间查询。线段树或者树状数组都可以。注意要离散化

class Solution {  public:      int c[100005];      int n;      map<int,int> m;      vector<int> countSmaller(vector<int>& nums) {            vector<int> a = nums;          sort(a.begin(),a.end());          for(int i=0;i<a.size();i++)          {              m[a[i]]=i+1;          }          n=nums.size();          vector<int> ans;            for(int i=n-1;i>=0;i--)          {              ans.push_back(sum(m[nums[i]]-1));              update(m[nums[i]]);          }            reverse(ans.begin(),ans.end());          return ans;        }        int lowbit(int x)      {          return x&(-x);      }        void update(int pos)      {          while(pos<=n)          {              c[pos]++;              pos+=lowbit(pos);          }      }        int sum(int pos)      {          int ans=0;          while(pos>0)          {              ans+=c[pos];              pos-=lowbit(pos);          }          return ans;      }  };