树状数组

lowbit运算

lowbit(x) = x&(-x)
取x的二进制表示最右边的1和它右边的所有0.结果一定是2的次幂。
例如：

定义

树状数组C仍是一个数组，与前缀和数组sum类似，它是一个用来记录和的数组，只不过它存放的不是前i个整数之和，而是在i号位之前(含i号位)lowbit(i)个整数之和。
C[i]的覆盖长度是lowbit(i),也可以理解成管辖范围。它是2的幂次，如1，2，4，8等。

• 两个操作
  getSum(x)返回前x个数之和A[1]+...+A[x]
  update(x,v)将第x个数加上v，即A[x]+=v

树状数组的应用

思路：
若使用hash数组的解法，其中hash[x]表示记录整数x当前的出现次数。接着，从右到左遍历序列,如果当前访问的是A[i],就令hash[A[i]]加1，表示当前整数A[i]的出现次数增加了一次。最后，序列中在A[i]右边比A[i]小的数等于hash[1]+hash[2]+...+hash[A[i]-1]的值。这两个工作可以通过update(A[i],1)和getSum(A[i]-1)来解决。

const int max_n = 100010;
#define lowbit(i) ((i)&(-i))
int c[max_n];
class Solution {
public:
    void update(int x,int v)
    {
        for(int i=x;i<max_n;i+=lowbit(i)){
            c[i]+=v;
        }
    }
    int getSum(int x){
        int sum = 0;
        for(int i=x;i>0;i-=lowbit(i)){
            sum+=c[i];
        }
        return sum;
    }

    vector<int> countSmaller(vector<int>& nums) {
        vector<int>ans;
        if(nums.empty()) return ans;
        ans.resize(nums.size());
        memset(c,0,sizeof(c));
        // 离散化
        vector<int>xs;
        for(int i=0;i<nums.size();++i)
            xs.push_back(nums[i]);
        sort(xs.begin(),xs.end());
        auto e = unique(xs.begin(),xs.end());
        for(int i=0;i<nums.size();++i)
            nums[i] = lower_bound(xs.begin(),e,nums[i])-xs.begin()+1;
        for(auto t:nums)
            cout<<t<<" ";
        cout<<endl;
        for(int i=nums.size()-1;i>=0;--i)
        {
            update(nums[i],1);
            ans[i] = getSum(nums[i]-1);
        }
        return ans;

    }
};

其他技巧：
如果要求数组下标在区间[x,y]内的数之和，即A[x]+A[x+1]+...A[y]可以转换成getSum(y)-getSum(x-1)来解决。

问题2

法一 树状数组

class Solution {
public:
    vector<int> c;
    int N;
    int lowbit(int i)
    {
        return i & (-i);
    }
    void update(int x,int v)
    {
        for(int i=x;i<N;i+=lowbit(i)){
            c[i]+=v;
        }
    }

    int getSum(int x) {
        int res = 0;
        for(int i=x;i>0;i-=lowbit(i))
            res += c[i];
        return res;
    }
    int reversePairs(vector<int>& nums) {
        // 离散化为排名
        set<int> s(nums.begin(), nums.end());
        map<int, int> m;
        for (auto x : s) {
            m[x] = m.size() + 1;
        }
        vector<int> ranks(nums.size(), 0);
        for (int i = 0; i < ranks.size(); ++i) {
            ranks[i] = m[nums[i]];
        }
        // 初始化树状数组
        N = ranks.size() + 1;
        c = vector<int>(N + 1, 0);
        // 从后向前遍历查询更新，并获取结果
        int res = 0;
        for (int i = ranks.size() - 1; i >= 0; --i) {
            // 确定只有一半大小的数的排名
            int t = (nums[i] > 0) ? ((nums[i] - 1) / 2) : (nums[i] / 2 - 1);
            auto it = m.lower_bound(t+1);
            // 统计小于这个排名的数
            if (it != m.begin()) {
                res += getSum((--it)->second);
            }
            // 新增这个数的排名
            update(ranks[i], 1);
        }
        return res;
    }
};

法二 归并排序

• 思路 将翻转对的统计视为归并排序完成的一个附加任务。

  class Solution {
  public:
    void mergeSort(vector<int>& nums,int left,int right,int& ans)
    {
        if(left==right) return;
        int mid = (left+right)>>1;
        mergeSort(nums,left,mid,ans);
        mergeSort(nums,mid+1,right,ans);
        merge(nums,left,right,ans);
    }
    void merge(vector<int>& nums,int left,int right,int& ans)
    {
        int mid = (left+right)>>1;
        int i = left;
        int j = mid+1;
        int m = left;
        int n = mid+1;
        while(m<=mid&&n<=right)
        {
  
            if(m<=mid&&nums[m]>2LL*nums[n]) {
                ans+=(mid-m+1);
                ++n;
  
            }
            else ++m;
  
        }
        vector<int>tmp;
        while(i<=mid&&j<=right)
        {
            if(nums[i]<=nums[j])
            {
                tmp.push_back(nums[i++]);
            }
            else {
                tmp.push_back(nums[j++]);
  
            }
        }
        while(i<=mid)
            tmp.push_back(nums[i++]);
        while(j<=right)
            tmp.push_back(nums[j++]);
        int k = 0;
        for(int i=left;i<=right;++i)
            nums[i]=tmp[k++];
    }
  
    int reversePairs(vector<int>& nums) {
        if(nums.empty()) return 0;
        int ans = 0;
        mergeSort(nums,0,nums.size()-1,ans);
         return ans;
    }
  };