GoLang: Range Sum Query on Immutable Array via Prefix Sum

Given an integer array nums, handle multiple queries of the following type:

Calculate the sum of the elements of nums 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 nums between indices left and right inclusive (i.e. nums[left] + nums[left + 1] + ... + nums[right]). Example 1: Input

1 2	[“NumArray”, “sumRange”, “sumRange”, “sumRange”] [[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]

[“NumArray”, “sumRange”, “sumRange”, “sumRange”]
[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]

Output

1	[null, 1, -1, -3]

[null, 1, -1, -3]

Explanation

1 2 3 4

NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]); numArray.sumRange(0, 2); // return (-2) + 0 + 3 = 1 numArray.sumRange(2, 5); // return 3 + (-5) + 2 + (-1) = -1 numArray.sumRange(0, 5); // return (-2) + 0 + 3 + (-5) + 2 + (-1) = -3

NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]);
numArray.sumRange(0, 2); // return (-2) + 0 + 3 = 1
numArray.sumRange(2, 5); // return 3 + (-5) + 2 + (-1) = -1
numArray.sumRange(0, 5); // return (-2) + 0 + 3 + (-5) + 2 + (-1) = -3

Prefix Sum Algorithm to compute the Range Query over Immutable List

Since the array or list is immutable, we can allocate a prefix sum array to store the prefix sum of the array. Then, the range sum query can be computed via two prefix sum. For example, sum(i, j) = prefixSum(j + 1) – prefixSum(i). We can pad one zero in the begining to handle the out of bounary problem.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

type NumArray struct {
    prefix []int
}
 
func Constructor(nums []int) NumArray {
    var prefix = make([]int, len(nums) + 1)
    prefix[0] = 0
    for i := 1; i <= len(nums); i ++ {
        prefix[i] += prefix[i - 1] + nums[i - 1]
    }
    return NumArray{prefix: prefix}
}
 
func (this *NumArray) SumRange(left int, right int) int {
    return this.prefix[right + 1] - this.prefix[left]
}
 
/**
 * Your NumArray object will be instantiated and called as such:
 * obj := Constructor(nums);
 * param_1 := obj.SumRange(left,right);
 */

type NumArray struct {
    prefix []int
}

func Constructor(nums []int) NumArray {
    var prefix = make([]int, len(nums) + 1)
    prefix[0] = 0
    for i := 1; i <= len(nums); i ++ {
        prefix[i] += prefix[i - 1] + nums[i - 1]
    }
    return NumArray{prefix: prefix}
}

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

/**
 * Your NumArray object will be instantiated and called as such:
 * obj := Constructor(nums);
 * param_1 := obj.SumRange(left,right);
 */

The time and space complexity is O(N) where N is the number of the elements in the array.

Range Query via Prefix Sum:

• Teaching Kids Programming – Prefix Sum Algorithm to Compute the Interval Sums
• C++ Range Sum Query – Immutable
• GoLang: Range Sum Query on Immutable Array via Prefix Sum

–EOF (The Ultimate Computing & Technology Blog) —