could not figure out what's wrong with my c++ BIT solution HELP


  • 0
    T

    I thought about my solution for a very long time, couldn't figure out what's wrong. It bothers me a lot. Any insight is appreciated!!
    More Details
    Errors:
    Input:
    [-2,5,-1]
    -2
    2
    Output:
    197
    Expected:
    3

    The same idea as 315 Count of smaller numbers after self.

    1. get the all sums from[0,i] as sum[i]

    2. sort sum vector as clone vector, and reindex elements in sum according to its index in clone vector. Put sum element value as map reflect's key, new index as reflect's value.
      3.add vector sum element from back to front, and at the same time find valid elements index range [idx1,idx2] in clone which satisfies the lowerbound and upperbound condition.

    3. get the sum from node 0 to node idx1 and sum from node 0 to node idx2 in our BIT. If the node is inserted into the BIT already we will find the node in our BIT. So we can know the node amount in BIT which satisfies our bound condition.

       class Solution {
       public:
      vector<long>tree,clone;
      int countRangeSum(vector<int>& nums, int lower, int upper) {
       int n=nums.size();
       vector<long>sum(n+1);
       for(int i=1;i<=n;i++)
       sum[i]=sum[i-1]+nums[i-1];// step1
       
      clone=sum;
      sort(clone.begin(),clone.end());
      tree.resize(sum.size()+1);
      unordered_map<long,int>reflect;
      for(int i=0;i<clone.size();i++)
      reflect[clone[i]]=i;//step2
      
       int res=0;
       for(int i=sum.size()-1;i>=0;i--)
       {
           
           int idx1=binarysearch(sum[i]+lower,true);
           int idx2=binarysearch(sum[i]+upper,false);
    
           res=res+count(idx2)-count(idx1);
           add(reflect[sum[i]]); //step3
       }
       return res;
    }
    
    
     int binarysearch(long val, bool includeself)
     {  
     if(includeself)
     return lower_bound(clone.begin(),clone.end(),val)-clone.begin();
     return upper_bound(clone.begin(),clone.end(),val)-clone.begin();
    

    }

    void add(int pos){
        pos=pos+1;
        while(pos<tree.size())
        {
            tree[pos]++;
            pos=pos+(pos&-pos);
        }
    }
    
    int count(int pos){
        int cnt=0;
        pos=pos+1;
        while(pos>0)
        {
            cnt=cnt+tree[pos];
            pos=pos-(pos&-pos);
        }
        return cnt;
    }
    

    };


Log in to reply
 

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