Dynamic Range Minimum Queries

class SegmentTree:
  def __init__(self, data):
    self.n = len(data)
    self.tree = [0] * (2 * self.n)
    self.build(data)

  def build(self, data):
    # Initialize leaves of the tree
    for i in range(self.n):
      self.tree[self.n + i] = data[i]
    # Build the tree by calculating parents
    for i in range(self.n - 1, 0, -1):
      self.tree[i] = min(self.tree[2 * i], self.tree[2 * i + 1])

  def update(self, pos, value):
    # Update the leaf node
    pos += self.n
    self.tree[pos] = value
    # Recalculate parents
    while pos > 1:
      pos //= 2
      self.tree[pos] = min(self.tree[2 * pos], self.tree[2 * pos + 1])

  def range_min(self, left, right):
    # Get the minimum value in the range [left, right)
    left += self.n
    right += self.n
    min_value = float('inf')

    while left < right:
      # left is a right child
      if left % 2 == 1: 
        min_value = min(min_value, self.tree[left])
        left += 1
      # right is a right child
      if right % 2 == 1:
        right -= 1
        min_value = min(min_value, self.tree[right])

      left //= 2
      right //= 2
    return min_value

def main():
  n, q = map(int, input().split())
  array = list(map(int, input().split()))
  
  seg_tree = SegmentTree(array)
  results = []
  
  for i in range(2, 2 + q):
    query = list(map(int, input().split()))
    if query[0] == 1:
      # Update query
      _, k, u = query
      # Convert to 0-based index
      seg_tree.update(k - 1, u)
    elif query[0] == 2:
      # Range minimum query
      _, a, b = query
      # Convert to 0-based index
      result = seg_tree.range_min(a - 1, b)
      results.append(result)
  
  print("\n".join(map(str, results)))

if __name__ == "__main__":
    main()

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED