class NumArray(val nums: IntArray) {
private val tree = IntArray(2 * nums.size)
init {
build(0, 0, nums.size - 1)
}
private fun build(v: Int, tl: Int, tr: Int) {
if (tl > tr) return
if (tl == tr) {
tree[v] = nums[tl]
} else {
val mid = tl + (tr - tl) / 2
build(2 * v + 1, tl, mid)
build(2 * v + 2, mid + 1, tr)
tree[v] = tree[2 * v + 1] + tree[2 * v + 2]
}
}
fun update(index: Int, `val`: Int) {
fun set(v: Int, tl: Int, tr: Int) {
if (tl == tr) {
tree[v] = `val`
return
}
val mid = (tl + tr) / 2
if (index <= mid)
set(2 * v + 1, tl, mid)
else
set(2 * v + 2, mid + 1, tr)
tree[v] = tree[2 * v + 1] + tree[2 * v + 2]
}
set(0, 0, nums.size - 1)
}
fun sumRange(left: Int, right: Int): Int {
fun sum(v: Int, tl: Int, tr: Int): Int =
if (left > tr || right < tl)
0
else if (tl >= left && tr <= right)
tree[v]
else {
val mid = (tl + tr) / 2
sum(2 * v + 1, tl, mid) + sum(2 * v + 2, mid + 1, tr)
}
return sum(0, 0, nums.size - 1)
}
}