c++ prefix sum


  • 0

    Construct array with prefix sum takes O(n) time.
    sumRange takes constant time O(1).

    class NumArray {
    public:
        NumArray(vector<int> nums) {
            pref.assign(nums.size() + 1, 0);
            for (int i = 0; i < nums.size(); ++i) pref[i + 1] = nums[i] + pref[i];
        }
        
        int sumRange(int i, int j) {
            return pref[j + 1] - pref[i];
        }
    private:
        vector<int> pref;
    };
    

Log in to reply
 

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