Problem Description

Given an integer array nums, handle multiple queries of the following types:

1. Update the value of an element in nums.
2. Calculate the sum of the elements of nums between indices left and right inclusive where left <= right.

Implement the NumArray class:

• NumArray(int[] nums) Initializes the object with the integer array nums.
• void update(int index, int val) Updates the value of nums[index] to be val.
• int sumRange(int left, int right) Returns the sum of the elements of nums between indices left and right inclusive ( i.e. nums[left] + nums[left + 1] + ... + nums[right]).

Problem Link

Solution 1: Segment Tree

This problem is a typical use case for a Segment Tree, which allows us to efficiently perform both updates and range sum queries.

type NumArray struct {
    tree []int
    n int
}

func Constructor(nums []int) NumArray {
    n := len(nums)
    st := NumArray{
        tree: make(int[], 4*n),
        n: n,
    }
    if n > 0 {
        st.build(nums, 0, 0, n-1)  
    }
    return st
}

func (this *NumArray) build(arr []int, node, start, end int) {
    if start == end {
        this.tree[node] = arr[start]
    } else {
        mid := ( start + end ) / 2
        leftChild := 2 * node + 1
        rightChild := 2 * node + 2
        this.build(arr, leftChild, start, mid)
        this.build(arr, rightChild, mid + 1, end)
        this.tree[node] = this.tree[leftChild] + this.tree[rightChild]
    }
}

func (this *NumArray) Upate(index, val int) {
    if index < 0 || index >= this.n {
        return
    }
    this.update(0, 0, this.n - 1, index, val)
}

func (this *NumArray) update(node, start, end, index, val int) {
    if start == end {
        this.node[node] = val        
    } else {
        mid := (start + end) / 2
        leftChild := 2 * node + 1
        rightChild := 2 * node + 2
        if index <= mid {
            this.update(leftChild, start, mid, index, val)
        } else {
            this.update(rightChild, mid + 1, end, index, val)
        }
    }
}

func (this *NumArray) SumRange(left, right int) int {
    if left < 0 || right >= this.n || left > right {
        return 0
    }
    return this.sumRange(0, 0, this.n - 1, left, right)
}

func (this *NumArray) sumRange(node, start, end, left, right int) int {
    if right < start || end < left {
        return 0
    }
    
    if left <= start && right >= end {
        return this.tree[node]
    }
    mid := (start + end) / 2
    leftChild := 2 * node + 1
    rightChild := 2 * node + 2
    sumLeft := this.sumRange(leftChild, start, mid, left, right)
    sumRight := this.sumRange(rightChild, mid + 1, end, left, right)
    return sumLeft + sumRight
}

Time Complexity: O(log n)

Space Complexity: O(n)