303. Range Sum Query - Immutable #

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:

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

Main idea of the problem #

Given an integer array nums，find the sum of the elements in the range from index i to j (i ≤ j), including i, j .

Example：

Given nums = [-2, 0, 3, -5, 2, -1]，the sum function is sumRange()

sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3

Explanation:

You can assume the array is immutable.
The sumRange method will be called multiple times.

Solution ideas #

Given an array，the numbers in the array are all**immutable**，design a data structure that can satisfy querying the sum of elements in any interval of the array.
In this problem, since the elements in the array are all**immutable**，therefore 2 methods can be used to solve it，the first solution is to use prefixSum，calculating the sum of elements in the interval by subtracting prefix sums，the initialization time complexity is O(n)，but the time complexity for querying the sum of interval elements is O(1)。The second solution is to use a segment tree，construct a segment tree，the parent node stores the sum of its two child nodes，the time complexity of initializing and building the tree is O(log n)，the time complexity for querying the sum of interval elements is O(log n)。

Code #


package leetcode

import (
	"github.com/halfrost/leetcode-go/template"
)

//Solution one Segment tree，sumRange time complexity O(1)

// NumArray define
type NumArray struct {
	st *template.SegmentTree
}

// Constructor303 define
func Constructor303(nums []int) NumArray {
	st := template.SegmentTree{}
	st.Init(nums, func(i, j int) int {
		return i + j
	})
	return NumArray{st: &st}
}

// SumRange define
func (ma *NumArray) SumRange(i int, j int) int {
	return ma.st.Query(i, j)
}

//Solution two prefixSum，sumRange time complexity O(1)

// // NumArray define
// type NumArray struct {
// 	prefixSum []int
// }

// // Constructor303 define
// func Constructor303(nums []int) NumArray {
// 	for i := 1; i < len(nums); i++ {
// 		nums[i] += nums[i-1]
// 	}
// 	return NumArray{prefixSum: nums}
// }

// // SumRange define
// func (this *NumArray) SumRange(i int, j int) int {
// 	if i > 0 {
// 		return this.prefixSum[j] - this.prefixSum[i-1]
// 	}
// 	return this.prefixSum[j]
// }

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