Short Binary Indexed tree (BIT or Fenwick tree) based C++ solution (1720 ms)


  • 2
    D

    You can do

    • O(1) update, O(N) sumRange
    • O(N) update, O(1) sumRange
    • O(NlogN) update, O(NlogN) sumRange

    Since here, the update and sumRange operations are distributed evenly, option 3 is more appropriate. Basically, we can use a segment tree to achieve that. For this speical case, we can use a simplified version: binary indexed tree (BIT), in which a linear array BITSum is used and the "pointers" can be calculted directly as array indices. BITSum[i] is the sum of num[i-x+1::i] (note i starts from 1), where x is the value respresented by the rightmost "1" bit of i (e.g. i=5 =>x=1; i=4=>x=4). x can be calculated as x = i - i &-i (i &-i reset the rightmost "1" bit to 0). More details can be found online.

    class NumArray {
    private:   
        int nSize;
        vector<int> BITsum; // BIT sum array
        vector<int> num; // original nums array
        
        int getSum(int i)
        {
            if(i<=0 || i>nSize) return 0;
            int res=BITsum[i];
            while( (i -= i & -i) > 0 )
                res +=BITsum[i];
            return res;
        }
    public:
        NumArray(vector<int> &nums) {
            nSize = nums.size();
            num = BITsum = vector<int>(nSize+1, 0);
            for(int i=0;i<nSize; ++i)
                update(i, nums[i]);
        }
    
        void update(int i, int val) {
            int delta = val - num[++i];
            for(num[i] = val;i<=nSize;i += i & -i)
                BITsum[i] +=delta;
        }
    
        int sumRange(int i, int j) {
            return (i>j || i<0 || j>=nSize)? 0: i==j?num[i+1]:( getSum(j+1) - getSum(i) );
        }
    };

Log in to reply
 

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