C++ 1728ms solution, O(n) space, O(sqrt(n)) time


  • 1
    class NumArray {
    
    private:
        vector<int> preSum;
        int windsz;
    public:
        NumArray(vector<int> &nums) {
        preSum = nums;
        windsz = sqrt(nums.size());
        for (int i=0;i<preSum.size();i++){
            if (i%windsz!=0)
                preSum[i]+=preSum[i-1];
        }
    }
    
    void update(int i, int val) {
        int datai = i%windsz==0?preSum[i]:preSum[i]-preSum[i-1];
        int diff=val-datai;
        if (diff==0) return;
        for (int j=i;j<(i/windsz+1)*windsz && j<preSum.size();j++){
            preSum[j]+=diff;
        }
    
    }
    
    int sumRange(int i, int j) {
        int res=0;
        int wi = i/windsz,wj=j/windsz;
        int datai = i%windsz==0?preSum[i]:preSum[i]-preSum[i-1];
        if (wi==wj) return preSum[j]-preSum[i]+datai;
        else{
            res+=preSum[(wi+1)*windsz-1]-preSum[i]+datai;
            res+=preSum[j];
            for (int k=wi+1;k<wj;k++){
                res+=preSum[(k+1)*windsz-1];
            }
            return res;
        }
    }
    };

Log in to reply
 

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