My solution using Binary Index Tree (1700+ms)


  • 1
    S

    class NumArray {

    public:

    vector<int> binaryIndexTree;
    vector<int> Nums;
    
    int lowBit(int n){
    	return n&((n-1)^n);
    }
    
    int getSum(int i){
    	int res=0;
    	while(i>0){
    		res+=binaryIndexTree[i];
    		i=i-lowBit(i);
    	}
    	return res;
    }
    
    NumArray(vector<int> &nums) {
        Nums=nums;
    	binaryIndexTree.assign(nums.size()+1,0);
        for(int i=1;i<=nums.size();i++){
        	binaryIndexTree[i]+=nums[i-1];
        	if(lowBit(i)+i<=nums.size())
            	binaryIndexTree[lowBit(i)+i]+=binaryIndexTree[i];
        }
    }
    
    void update(int i, int val) {
    	int error=val-Nums[i];
    	Nums[i]=val;
        i++;
        while(i<binaryIndexTree.size()){
        	binaryIndexTree[i]+=error;
        	i=lowBit(i)+i;
        }
    }
    
    int sumRange(int i, int j) {
        int sumJ=getSum(j+1);
        int sumI=getSum(i);
        return sumJ-sumI;
    }
    

    };


Log in to reply
 

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