307. Range Sum Query - Mutable #

Problem #

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

The update(i, val) function modifies nums by updating the element at index i to val.

Example:

Given nums = [1, 3, 5]

sumRange(0, 2) -> 9
update(1, 2)
sumRange(0, 2) -> 8

Note:

The array is only modifiable by the update function.
You may assume the number of calls to update and sumRange function is distributed evenly.

Problem Summary #

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

The update(i, val) function can modify the array by updating the value at index i to val.

Example:

Given nums = [1, 3, 5]

sumRange(0, 2) -> 9  
update(1, 2)  
sumRange(0, 2) -> 8

Note:

The array can only be modified through the update function.
You may assume the number of calls to the update function and the sumRange function is distributed evenly.

Solution Ideas #

Given an array where all the numbers are **mutable**, design a data structure that can support querying the sum of elements in any interval of the array.
Compared with Problem 303, since the elements in this problem are all mutable, the first solution that comes to mind is a segment tree. Build a segment tree where each parent node stores the sum of its two child nodes. The time complexity for initializing and building the tree is O(log n), the time complexity for querying the sum of elements in an interval is O(log n), and the time complexity for updating an element value is O(log n).
What if this problem is still solved using the prefixSum approach? Then the time complexity of each update operation is O(n), because every time a value is changed, in the worst case all prefixSum values must be updated once. The prefixSum method can also AC for this problem, but its time ranking is only 5%, which is very poor.
This problem can also be solved using a Binary Indexed Tree. The code is very straightforward: an interval query is simply the difference between two interval prefix sums. This is the simplest application of a Binary Indexed Tree.

Code #


package leetcode

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

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

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

// Update define
func (this *NumArray) Update(i int, val int) {
	this.st.Update(i, val)
}

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

//Solution 2: prefixSum, sumRange time complexity O(1)

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

// // Constructor307 define
// func Constructor307(nums []int) NumArray307 {
// 	data := make([]int, len(nums))
// 	for i := 0; i < len(nums); i++ {
// 		data[i] = nums[i]
// 	}
// 	for i := 1; i < len(nums); i++ {
// 		nums[i] += nums[i-1]
// 	}
// 	return NumArray307{prefixSum: nums, data: data}
// }

// // Update define
// func (this *NumArray307) Update(i int, val int) {
// 	this.data[i] = val
// 	this.prefixSum[0] = this.data[0]
// 	for i := 1; i < len(this.data); i++ {
// 		this.prefixSum[i] = this.prefixSum[i-1] + this.data[i]
// 	}
// }

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

// Solution 3: Binary Indexed Tree
// type NumArray struct {
// 	bit  template.BinaryIndexedTree
// 	data []int
// }

// // Constructor define
// func Constructor307(nums []int) NumArray {
// 	bit := template.BinaryIndexedTree{}
// 	bit.InitWithNums(nums)
// 	return NumArray{bit: bit, data: nums}
// }

// // Update define
// func (this *NumArray) Update(i int, val int) {
// 	this.bit.Add(i+1, val-this.data[i])
// 	this.data[i] = val
// }

// // SumRange define
// func (this *NumArray) SumRange(i int, j int) int {
// 	return this.bit.Query(j+1) - this.bit.Query(i)
// }

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