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;      }  };