Leetcode - Range Sum Query - Mutable

https://leetcode.com/problems/range-sum-query-mutable/

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

This is a typical segment tree usage. It should be recited.

type NumArray struct {
    root *SegmentTree
}

type SegmentTree struct {
    start int
    end int
    left *SegmentTree
    right *SegmentTree
    sum int
}

func Constructor(nums []int) NumArray {
    return NumArray{
        root: buildTree(nums, 0, len(nums)-1),
    }
}

func buildTree(nums []int, start, end int) *SegmentTree {
    if start > end {
        return nil
    }
    result := &SegmentTree{
        start: start,
        end: end,
    }
    if start == end {
        result.sum = nums[start]
        return result
    }
    mid := (start+end)/2
    result.left = buildTree(nums, start, mid)
    result.right = buildTree(nums, mid+1, end)
    result.sum = result.left.sum + result.right.sum
    
    return result
}


func (this *NumArray) Update(i int, val int)  {
    update(this.root, i, val)
}

func update(root *SegmentTree, pos, val int) {
    if root.start == root.end {
        root.sum = val
        return
    }
    mid := (root.start + root.end)/2
    if pos <= mid {
        update(root.left, pos, val)
    } else {
        update(root.right, pos, val)
    }
    root.sum = root.left.sum + root.right.sum
}


func (this *NumArray) SumRange(i int, j int) int {
    return sumRange(this.root, i, j)
}

func sumRange(root *SegmentTree, start, end int) int {
    if root.start == start && root.end == end {
        return root.sum
    }
    mid := (root.start+root.end)/2
    if end <= mid {
        return sumRange(root.left, start, end)
    } else if start > mid {
        return sumRange(root.right, start, end)
    } 
    return sumRange(root.left, start, mid) + sumRange(root.right, mid+1, end)    
}


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

• 相关文章
• 全局相关文章