## Range Sum Query Immutable

07/17/2016 Dynamic Programming

## Question

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:

1. You may assume that the array does not change.
2. There are many calls to sumRange function.

## Solution

Result: Accepted Time: 576 ms

Here should be some explanations.

struct NumArray {
int * ary;
int cnt;

};

/** Initialize your data structure here. */
struct NumArray* NumArrayCreate(int* nums, int numsSize) {
struct NumArray * numAry = (struct NumArray *)malloc(sizeof(struct NumArray));
int * ptr = (int * ) malloc((numsSize + 5)*sizeof(int));
numAry->ary = ptr;
numAry->cnt = numsSize;
*ptr = 0;
int sum = 0;
while(numsSize--)
{
sum += *(nums++);
*(++ptr) = sum;
}
return numAry;
}

int sumRange(struct NumArray* numArray, int i, int j) {

return numArray->ary[j+1] - numArray->ary[i];
}

/** Deallocates memory previously allocated for the data structure. */
void NumArrayFree(struct NumArray* numArray) {
//free(numArray->ary);
//free(numArray);

}

// Your NumArray object will be instantiated and called as such:
// struct NumArray* numArray = NumArrayCreate(nums, numsSize);
// sumRange(numArray, 0, 1);
// sumRange(numArray, 1, 2);
// NumArrayFree(numArray);


Complexity Analytics

• Time Complexity: $O(n)$
• Space Complexity: $O(1)$