LeetCode #303 Range Sum Query — Immutable

Easy

Problem

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

By building a prefix sum list, sum in each range can be easily calculated.

Complexity

It takes O(n) time to build the prefix sum list if n denotes to the length of nums. However, each query only needs O(1) time for getting result.

Also, it needs O(n) extra space for maintaining prefix sum list.