My AC solution using Binary Indexed Tree - O(log n) time and O(n) space


  • 0
    P
    class NumArray {
    private:
        std::vector<int> bitTree;
        std::vector<int>& inputArr;
        int mLen;
        void updateDiff(int i, int diff){
            i++;
            while(i <= mLen){
                bitTree[i] += diff;
                i = getNext(i);
            }    
        }
        
        int getPrevious(int index){
            return index & (index-1);
        }
        
        int getNext(int index){
            return 2*index-(index & (index-1));
        }
        
        void createBIT(){
            for(int i=0; i< mLen; i++){
                updateDiff(i, inputArr[i]);
            }
        }
    
        
    public:
        NumArray(vector<int> &nums):inputArr(nums), mLen(nums.size()) 
                                    ,bitTree(nums.size()+1, 0) 
        {
            createBIT();
        }
        
        void update(int i, int val) {
            updateDiff(i, val-inputArr[i]);
            inputArr[i] = val;
        }
    
        int sumRange(int i, int j) {
            if(i > 0){
                return sumRange(0, j)- sumRange(0, i-1);
            }
            j++;
            int sum = 0;
            while (j > 0) {
                sum += bitTree[j];
                j = getPrevious(j);
            }
            return sum;
        }
    };

Log in to reply
 

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