> For the complete documentation index, see [llms.txt](https://txfs19260817.gitbook.io/leetcode-go-notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://txfs19260817.gitbook.io/leetcode-go-notes/solutions/303.-range-sum-query-immutable.md).

# 303. Range Sum Query - Immutable

## LeetCode [303. Range Sum Query - Immutable](https://github.com/txfs19260817/LeetCode-Go/blob/master/solutions/title/README.md)

### Description

Given an integer array `nums`, find the sum of the elements between indices `left` and `right` inclusive, where `(left <= right)`.

Implement the `NumArray` class:

* `NumArray(int[] nums)` initializes the object with the integer array `nums`.
* `int sumRange(int left, int right)` returns the sum of the elements of the `nums` array in the range `[left, right]` inclusive (i.e., `sum(nums[left], nums[left + 1], ... , nums[right])`).

**Example 1:** **Input** \["NumArray", "sumRange", "sumRange", "sumRange"] \[\[\[-2, 0, 3, -5, 2, -1]], \[0, 2], \[2, 5], \[0, 5]] **Output** \[null, 1, -1, -3] **Explanation** NumArray numArray = new NumArray(\[-2, 0, 3, -5, 2, -1]); numArray.sumRange(0, 2); // return 1 ((-2) + 0 + 3) numArray.sumRange(2, 5); // return -1 (3 + (-5) + 2 + (-1)) numArray.sumRange(0, 5); // return -3 ((-2) + 0 + 3 + (-5) + 2 + (-1))

**Constraints:**

* `1 <= nums.length <= 104`
* `-105 <= nums[i] <= 105`
* `0 <= left <= right < nums.length`
* At most `104` calls will be made to `sumRange`.

### Tags

Dynamic Programming, Design

### Solution

We can pre-compute a cumulative array sum with respect to the origin at index 0, with the formula: $$sum\[i]=sum\[i-1]+nums\[i]$$. Then we can formulate the sum range with given i and j: $$sumRange(i,j)=sums\[j+1]−sums\[i]$$

### Complexity

* Time complexity: $$O(n)$$for initializing sum; $$O(1)$$ for performing search;
* Space complexity: $$O(n)$$

### Code

```go
type NumArray struct {
	sum []int
}

func Constructor(nums []int) NumArray {
	if len(nums) == 0 {
		return NumArray{}
	}
	sum := make([]int, len(nums)+1)
	for i, num := range nums {
		sum[i+1] = sum[i] + num
	}
	return NumArray{sum: sum}
}

func (this *NumArray) SumRange(left int, right int) int {
	return this.sum[right+1] - this.sum[left]
}
```

## Reference

1. [区域和检索 - 数组不可变](https://leetcode-cn.com/problems/range-sum-query-immutable/solution/qu-yu-he-jian-suo-shu-zu-bu-ke-bian-by-l-px41/)