303. Range Sum Query

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.

Solution: Note that there are many calls to sumRange function, so the tranverse method is inefficient(O(n^3)). We use the idea of cumulative histogram to build an array A of cumulative sums. A[i] is sum[0,i], sum(i,j)=A[j]-A[i-1](i!=0)

 1 class NumArray {
 2 private:
 3     vector<int> accumNums;
 4 public:
 5     NumArray(vector<int> nums) {
 6         accumNums=nums;
 7         for (int i=1;i<nums.size();i++){
 8             accumNums[i]+=accumNums[i-1]; //calculate the cumulative sums
 9         }
10     }
11     
12     int sumRange(int i, int j) {
13         return (i==0)? accumNums[j]:accumNums[j]-accumNums[i-1];
14     }
15 };
16 
17 /**
18  * Your NumArray object will be instantiated and called as such:
19  * NumArray obj = new NumArray(nums);
20  * int param_1 = obj.sumRange(i,j);
21  */