LeetCode: Range Sum Query – Mutable Posted on January 12, 2018July 26, 2020 by braindenny Range Sum Query – Mutable Similar Problems: Range Addition CheatSheet: Leetcode For Code Interview CheatSheet: Common Code Problems & Follow-ups Tag: #oodesign, #segmenttree, #rangesum Related Reading: Segment Tree by geeksforgeeks.org 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. What if, update and sumRange function is not distributed evenly? Let's say, the ratio of update_count/sumRange_count is 10000 or 0.0001? Github: code.dennyzhang.com Credits To: leetcode.com Leave me comments, if you have better ways to solve. // https://code.dennyzhang.com/range-sum-query-mutable // Basic Ideas: segment tree // // Complexity: Time O(log(n)), Space O(n) type NumArray struct { tree []int size int } func Constructor(nums []int) NumArray { // build segment tree // full binary tree: parent: i -> child: 2*i, 2*i+1 size := len(nums) // left node: len(nums), branch node: len(nums)-1 // To simplify the code, we add a dummy node. // Thus two parts have the same amount of nodes. // tree[1] would be the root, and tree[0] is dummy tree := make([]int, size*2) // assign left nodes for i, _ := range nums { tree[i+size] = nums[i] } // update parent nodes for i:=size-1; i>0; i-- { tree[i] = tree[i*2]+tree[i*2+1] } return NumArray{tree:tree, size:size} } func (this *NumArray) Update(i int, val int) { // update from bottom to up i += this.size this.tree[i] = val for i > 0 { // how to get parent node? l, r := i, i if i%2 == 0 { r = i+1 } else { l = i-1 } // update parent this.tree[i/2] = this.tree[l]+this.tree[r] i = i/2 } } func (this *NumArray) SumRange(i int, j int) int { // find the node from bottom to up res := 0 i, j = i+this.size, j+this.size // quit when size of range is 0 for i<=j { // add left subrange to the result, and move the pointer if (i%2) == 1 { res += this.tree[i] i++ } // add right subrange to the result, and move the pointer if (j%2) == 0 { res += this.tree[j] j-- } i, j = i/2, j/2 } return res } /** * Your NumArray object will be instantiated and called as such: * obj := Constructor(nums); * obj.Update(i,val); * param_2 := obj.SumRange(i,j); */ Post Views: 10