My C++ implemented segment tree base method with value discretization.


  • 0
    B

    My C++ implemented segment tree base method with value discretization.

    typedef long long ll;
    vector<ll> tree;
    void TreeInsert(int rt, int l, int r,int pos){
        if(l==r){
            tree[rt]++;
            return ;
        }
        int mid=(l+r)>>1;
        if(pos<=mid){
            TreeInsert(rt<<1, l, mid, pos);
        }else{
            TreeInsert(rt<<1|1, mid+1, r, pos);
        }
        tree[rt]++;
    }
    void TreeDelete(int rt, int l, int r, int pos){
        if(l==r){
            tree[rt]--;
            return;
        }
        int mid=(l+r)>>1;
        if(pos<=mid){
            TreeDelete(rt<<1, l, mid, pos);
        }else{
            TreeDelete(rt<<1|1, mid+1, r, pos);
        }
        tree[rt]--;
    }
    int TreeFind(int rt, int l, int r, int L, int R){
        if(l>=L&&r<=R){
            return tree[rt];
        }
        if(r<L||l>R){
            return 0;
        }
        int mid=(l+r)>>1;
        int ret=0;
        if(L<=mid){
            ret+=TreeFind(rt<<1, l, mid, L, R);
        }
        if(R>mid){
            ret+=TreeFind(rt<<1|1, mid+1, r, L, R);
        }
        return ret;
    }
    int countRangeSum(vector<int>& nums, int lower, int upper) {
        vector<ll> sum(nums.size()+1, 0);
        map<ll, int> mp;
        for(int i=0; i<nums.size(); ++i){
            sum[i+1]=sum[i]+nums[i];
            mp[sum[i+1]]=1;
        }
        for(int i=0; i<sum.size(); ++i){
            mp[lower+sum[i]]=1;
            mp[upper+sum[i]]=1;
        }
        tree.resize(mp.size()<<2, 0);
        int cnt=0;
        for(map<ll, int>::iterator it=mp.begin(); it!=mp.end(); ++it){
            it->second=++cnt;
        }
        for(int i=1; i<sum.size(); ++i){
            TreeInsert(1, 1, cnt, mp[sum[i]]);
        }
        int ans=0;
        for(int i=0; i<nums.size(); ++i){
            int _lower_index=mp[lower+sum[i]],
            _upper_index=mp[upper+sum[i]];
            ans+=TreeFind(1, 1, cnt, _lower_index, _upper_index);
            TreeDelete(1, 1, cnt, mp[sum[i+1]]);
        }
        cout<<INT_MAX<<"\t"<<INT_MIN<<endl;
        return ans;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.