Skip to content

Prepare For Coder Interview – Denny

  • Basic
  • Medium
  • Hard
  • Architect
  • Life

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);
 */
linkedin
github
slack

Post Views: 10
Posted in AmusingTagged #classic, oodesign, rangesum, segmenttree

Post navigation

LeetCode: Ransom Note
LeetCode: Sum of Left Leaves

Leave a Reply Cancel reply

Your email address will not be published.

Tags

#array #backtracking #bfs #binarytree #bitmanipulation #blog #classic #codetemplate #combination #dfs #dynamicprogramming #game #graph #greedy #heap #inspiring #interval #linkedlist #manydetails #math #palindrome #recursive #slidingwindow #stack #string #subarray #trie #twopointer #twosum binarysearch editdistance hashmap intervaldp knapsack monotone oodesign presum rectangle redo review rotatelist series sql treetraversal unionfind

Recent Posts

  • a
  • a
  • a
  • a
  • a

Recent Comments

    Archives

    Categories

    • Amusing
    • Basic
    • Easy
    • Hard
    • Life
    • Medium
    • Resource
    • Review
    • Series
    • Uncategorized
    Proudly powered by WordPress | Theme: petals by Aurorum.