307. Range Sum Query - Mutable

Problem Link

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]).

 

Example 1:

Input
["NumArray", "sumRange", "update", "sumRange"]
[[[1, 3, 5]], [0, 2], [1, 2], [0, 2]]
Output
[null, 9, null, 8]

Explanation
NumArray numArray = new NumArray([1, 3, 5]);
numArray.sumRange(0, 2); // return 1 + 3 + 5 = 9
numArray.update(1, 2);   // nums = [1, 2, 5]
numArray.sumRange(0, 2); // return 1 + 2 + 5 = 8

 

Constraints:

• 1 <= nums.length <= 3 * 104
• -100 <= nums[i] <= 100
• 0 <= index < nums.length
• -100 <= val <= 100
• 0 <= left <= right < nums.length
• At most 3 * 104 calls will be made to update and sumRange.

Solution

---

Python3

class LazySegmentTree:
  def __init__(self, arr):
    self.n = len(arr)
    self.tree = [0] * (4 * self.n)		
    self.lazy = [0] * (4 * self.n)
    self.build(1, 0, self.n - 1, arr)
 
  def build(self, v, tl, tr, arr):
    if tl == tr:
      self.tree[v] = arr[tl]
    else:
      tm = tl + (tr - tl) // 2
      self.build(v * 2, tl, tm, arr)
      self.build(v * 2 + 1, tm + 1, tr, arr)
      self.tree[v] = self.tree[v * 2] + self.tree[v * 2 + 1]
 
  def query(self, v, tl, tr, l, r):
    self.lazy_update(v, tl, tr)
    
    if l > r: return 0
 
    if tl == l and tr == r:
      return self.tree[v]
    else:
      tm = tl + (tr - tl) // 2
 
      return self.query(v * 2, tl, tm, l, min(tm, r)) + self.query(v * 2 + 1, tm + 1, tr, max(tm + 1, l), r)
 
  def lazy_update(self, v, tl, tr):
    if self.lazy[v] != 0:
      self.tree[v] += (tr - tl + 1) * self.lazy[v]
 
      if tl != tr:
        self.lazy[v * 2] += self.lazy[v]
        self.lazy[v * 2 + 1] += self.lazy[v]
 
      self.lazy[v] = 0
 
  def range_update(self, v, tl, tr, l, r, value):
    self.lazy_update(v, tl, tr)
    
    if l > r: return
      
    if tl == l and tr == r:
      self.lazy[v] += value
      self.lazy_update(v, tl, tr)
    else:
      tm = tl + (tr - tl) // 2
      
      self.range_update(v * 2, tl, tm, l, min(tm, r), value)
      self.range_update(v * 2 + 1, tm + 1, tr, max(tm + 1, l), r, value)
      self.tree[v] = self.tree[v * 2] + self.tree[v * 2 + 1]
    
  
  def update(self, v, tl, tr, pos, value):
    self.lazy_update(v, tl, tr)
    
    if tl == tr:
      self.tree[v] = value
    else:
      tm = tl + (tr - tl) // 2
 
      if pos <= tm:
        self.update(v * 2, tl, tm, pos, value)
      else:
        self.update(v * 2 + 1, tm + 1, tr, pos, value)
 
      self.tree[v] = self.tree[v * 2] + self.tree[v * 2 + 1]
 
class NumArray:
 
    def __init__(self, nums: List[int]):
        self.st = LazySegmentTree(nums)
        self.n = len(nums)
 
    def update(self, index: int, val: int) -> None:
        self.st.update(1, 0, self.n - 1, index, val)
 
    def sumRange(self, left: int, right: int) -> int:
        return self.st.query(1, 0, self.n - 1, left, right)
        
 
 
# Your NumArray object will be instantiated and called as such:
# obj = NumArray(nums)
# obj.update(index,val)
# param_2 = obj.sumRange(left,right)