LeetCode-327. 区间和的个数

传送门：https://leetcode.cn/problems/count-of-range-sum/
思路：归并排序 / 树状数组（线段树）
1.归并排序
首先是利用前缀和数组将问题转换为两数之差问题，对于前缀和 pre[i],寻找 j>i 且 pre[j]-pre[i] 位于 [lower,upper] 的下标 j 的个数
而归并排序的合并过程时，此时前后两个数组 pre[l,h] 和 pre[h+1,r]，对于已经是已排序状态了，那么对于前数组 pre[l,h]，是可以求得其对于后数组 pre[h+1,r] 的合法个数的。对于 pre[l,h]的下标 i ，已可求得在区间 [h+1,r], 而对于其它区间的 j 是可以在归并过程的其它过程中求得的。

2.树状数组（线段树）
同样是对于前缀和数组进行分析，对于 pre[i],当 j>i, pre[j] 位于区间 [pre[i]+lower, pre[i]+upper] 之间是合法的，因此可以从左到右遍历pre， 对于 pre[i],查询线段树中下标pre[i]的个数, 然后将区间 [pre[i]+lower, pre[i]+upper] 加1，需要注意将 pre[i]，pre[i]+lower, pre[i]+upper哈希离散化

Code 1.归并排序:

class Solution {
    int res;
    long long lower,upper;
    vector<long long> tmp;
public:
    int countRangeSum(vector<int>& nums, int lower, int upper) {
        int n=nums.size();
        vector<long long> dd(n+1);
        res=0;
        this->lower=lower;
        this->upper=upper;
        tmp.resize(n+1);
        for(int i=0;i<n;++i)
            dd[i+1]=dd[i]+nums[i];
        mergeSort(dd,0,n);
        return res;
    }

    void mergeSort(vector<long long> &nums,int l,int r){
        if(l==r){ return; }
        int h=l+(r-l)/2;
        mergeSort(nums,l,h);
        mergeSort(nums,h+1,r);
        for(int i=l;i<=r;++i)
            tmp[i]=nums[i];
        int ll=h+1,rr=h+1;
        for(int i=l;i<=h;++i)
        {
            while(rr<=r&&(tmp[rr]-tmp[i])<=upper){
                ++rr;
            }
            while(ll<rr&&(tmp[ll]-tmp[i])<lower){
                ++ll;
            }
            res+=rr-ll;
        }
        int l2=h+1,t=l;
        while(t<=r){
            if(l2==r+1){
                nums[t++]=tmp[l++];
            }else if(l==h+1){
                nums[t++]=tmp[l2++];
            }else if(tmp[l]<=tmp[l2]){
                nums[t++]=tmp[l++];
            }else{
                nums[t++]=tmp[l2++];
            }
        }
    }
};

code 2.数组数组

class Solution {
    vector<int> C;
public:
    int countRangeSum(vector<int>& nums, int lower, int upper) {
        int n=nums.size(),res=0;
        vector<long long> proN(n+1);
        for(int i=0;i<n;++i)
            proN[i+1]=proN[i]+nums[i];
        map<long long,int> mp;
        for(auto v:proN)
        {
            mp[v]=1;
            mp[v+lower]=1;
            mp[v+upper]=1;
        }
        int t=1;
        for(auto &v:mp)
            v.second=t++;
        C.resize(t);
        for(auto v:proN)
        {
            res+=query(mp[v]);
            update(mp[v+lower],1);
            update(mp[v+upper]+1,-1);
        }
        return res;
    }

    int lowbit(int x){
        return x&(-x);
    }

    void update(int id,int x){
        while(id<C.size()){
            C[id]+=x;
            id+=lowbit(id);
        }
    }

    int query(int id){
        int res=0;
        while(id>0){
            res+=C[id];
            id-=lowbit(id);
        }
        return res;
    }
};