303.range-sum-query-immutable.cpp

/*
 * @lc app=leetcode id=303 lang=cpp
 *
 * [303] Range Sum Query - Immutable
 *
 * https://leetcode.com/problems/range-sum-query-immutable/description/
 *
 * algorithms
 * Easy (38.58%)
 * Total Accepted:    146.4K
 * Total Submissions: 376.4K
 * Testcase Example:  '["NumArray","sumRange","sumRange","sumRange"]\n[[[-2,0,3,-5,2,-1]],[0,2],[2,5],[0,5]]'
 *
 * Given an integer array nums, find the sum of the elements between indices i
 * and j (i ≤ j), inclusive.
 * * Example:
 * 
 * Given nums = [-2, 0, 3, -5, 2, -1]
 * 
 * sumRange(0, 2) -> 1
 * sumRange(2, 5) -> -1
 * sumRange(0, 5) -> -3
 * 
 * 
 * 
 * Note:
 * 
 * You may assume that the array does not change.
 * There are many calls to sumRange function.
 * 
 * 
 */
class NumArray {
public:
    NumArray(vector<int>& nums) {
        partSum = vector<int>(nums.size() + 1);
        partSum[0] = 0;
        for (int i = 1; i <= nums.size(); ++i)
            partSum[i] = partSum[i-1] + nums[i-1];
        return;
    }
    
    int sumRange(int i, int j) {
       return partSum[j+1] - partSum[i];
    }
private:
    vector<int> partSum;
};

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray* obj = new NumArray(nums);
 * int param_1 = obj->sumRange(i,j);
 */