Medium

Range Sum Query Mutable

LAB

Apply updates [index,value] to nums and answer range-sum queries [left,right]. Return the query results.

EXAMPLES

Example 1

Input
{
  "nums": [
    1,
    3,
    5
  ],
  "updates": [
    [
      1,
      2
    ]
  ],
  "queries": [
    [
      0,
      2
    ],
    [
      0,
      2
    ]
  ]
}

Output
[
  9,
  8
]

FUNCTION SHAPE

nums: intArrayupdates: intMatrixqueries: intMatrix→intArray

SOLUTION NOTE

Direct application of sum segment tree template. This is the canonical segment tree problem.

Reveal reference solution +

pythonREFERENCE

class NumArray:
    def __init__(self, nums: List[int]):
        self.n = len(nums)
        self.tree = SegTree(nums, 0, self.n - 1)

    def update(self, index: int, val: int) -> None:
        self.tree.update(index, val)

    def sumRange(self, left: int, right: int) -> int:
        return self.tree.query(left, right)

TimeO(log n) per operation

SpaceO(n)

Open on LeetCode ↗