leetcode-go/leetcode/medium/307.range-sum-query-mutable.go

type NumArray struct {
	seg []int
	l   int
}

func Constructor(nums []int) (numArr NumArray) { // Segment tree, O(n) construction, O(logn) update, O(logn) sum range
	numArr.l = len(nums)
	numArr.seg = make([]int, 2*numArr.l)
	copy(numArr.seg[numArr.l:], nums)
	for i := numArr.l - 1; 0 < i; i-- {
		numArr.seg[i] = numArr.seg[2*i] + numArr.seg[2*i+1]
	}
	return
}

func (this *NumArray) Update(i int, val int) {
	i += this.l
	this.seg[i] = val
	for i = i / 2; 0 < i; i /= 2 {
		this.seg[i] = this.seg[2*i] + this.seg[2*i+1]
	}
}

func (this *NumArray) SumRange(i int, j int) (sum int) {
	for i, j = i+this.l, j+this.l; i < j; i, j = i/2, j/2 {
		if i%2 == 1 {
			sum += this.seg[i]
			i++
		}
		if j%2 == 0 {
			sum += this.seg[j]
			j--
		}
	}
	if i == j {
		sum += this.seg[i]
	}
	return
}

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