Znzryb's Blog
0%

327. 区间和的个数

Posted on Edited on

思路讲解

树状数组经典题。

然后前面看半天看不太懂，原来是用了频数数组呀，我想为啥要用树状数组那？

原来数组里维护的是频数，需要区间查询+单点修改两个操作，这个树状数组操作我还是会的。

频数数组
很多数据结构都是基于「频数数组」。
给定数组 t 以及它的下标范围 [L,R]，t[x] 就表示元素 x 在数据结构中的出现次数。基于此，上述的两个操作可以变为：
操作 1「查询」：给定一个范围 [left,right]，查询 t[left] 到 t[right] 的和；
操作 2「更新」：给定一个元素 x，将 t[x] 增加 1。
这也是线段树和树状数组的基础，它们需要的空间都与数组 t 的下标范围 [L,R] 正相关。在本题数据规模较大的情况下（例如测试数据中，出现了元素值达到 32 位有符号整数的上下界），线段树和树状数组都会超出空间限制，因此需要借助「离散化」操作，将这些元素映射到一个较小规模的区间内。
https://leetcode.cn/problems/count-of-range-sum/solutions/476205/xian-ren-zhi-lu-ru-he-xue-xi-ke-yi-jie-jue-ben-ti-/

AC代码

https://leetcode.cn/problems/count-of-range-sum/submissions/585372478/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
class Solution {
public:
    typedef long long ll;
    int countRangeSum(vector<int>& nums, int lower, int upper) {

        int n=nums.size();
        vector<ll> sumA(n+10,0);
        set<ll> li;// 离散化映射关系
        vector<ll> lii(n+10,-1e11+7);// 离散化映射关系数组
        for(int i=1;i<=n;++i){
            sumA[i]=sumA[i-1]+nums[i-1];
            // 0 index -> 1 index
            li.insert(sumA[i]);
        }
        // 我个人认为，就是每次查询查一下以该点为结尾的valid子数组有几个
        // 然后加入答案就行，在线算法
        // 实际上是个频数数组+树状数组
        vector<ll> BIT(n+10,0);
        ll distinctN=li.size();  // 去重以后的n大小
        ll idx=0;
        for(set<ll>::iterator it=li.begin();it!=li.end();it++){
            lii[++idx]=*it;
        }
        int ans=0;
        for(int i=1;i<=n;++i){
            ans+=search(sumA[i]-upper,sumA[i]-lower,
                BIT,lii,distinctN);
            add(sumA[i],BIT,lii,distinctN);
            if(sumA[i]>=lower && sumA[i]<=upper)
                ans+=1;
        }
        return ans;
    }
    inline ll lowbit(ll x){
        return x&(-x);
    }
    inline void pushup(vector<ll> &BIT,ll x,ll v,ll n){
        while(x<=n){
            BIT[x]+=v;
            x+=lowbit(x);
        }
    }
    inline void add(ll x,vector<ll> &BIT,const vector<ll> &lii,const ll n){
        ll idx=lower_bound(lii.begin()+1,
            lii.begin()+n+1,x)-lii.begin();
        if(lii[idx]!=x)
            idx-=1;
        pushup(BIT,idx,1,n);
    }
    inline ll search(ll l,ll r,vector<ll> &BIT,vector<ll> &lii,ll n){
        ll resl=0,resr=0;
        ll idxl=lower_bound(lii.begin()+1,
            lii.begin()+n+1,l)-lii.begin();
        ll idxr=lower_bound(lii.begin()+1,
            lii.begin()+n+1,r)-lii.begin();
        if(lii[idxr]!=r)
            idxr-=1;
        // 因为是两前缀和相减，l往后退一下。
        idxl-=1;
        while(idxl>0) {
            resl+=BIT[idxl];
            idxl-=lowbit(idxl);
        }
        while(idxr>0) {
            resr+=BIT[idxr];
            idxr-=lowbit(idxr);
        }
        // if(resr-resl<0)
        //     return 0LL;
        return resr-resl;
    }
};

心路历程（WA，TLE，MLE……）

唉这题搞了半天

记住，离散化之后，传入的数组大小应该是去重以后的大小（即ditinctN），否则搜出lii的递增范围，lower_bound()就不可靠了。

1
search(sumA[i]-upper,sumA[i]-lower,BIT,lii,distinctN);

https://leetcode.cn/problems/count-of-range-sum/submissions/585369029/

记得离散化映射关系数组的初始化值为0容易出事，因为如果是搜0，搜到外面去容易出事

1
vector<ll> lii(n+10,-1e11+7);// 离散化映射关系数组