Range Minimum Query with Point Update

Given an array nums, support point updates and range minimum queries. For every query operation, return the minimum value inside the requested interval. This is a standard segment tree use case for maintaining an aggregate under updates.

Input Format

nums = initial integer array, operations = sequence of updates and queries

Output Format

minimum for every type-2 query, in order

Constraints

  • 1 <= nums.length <= 10^5
  • 1 <= operations.length <= 10^5
  • Each operation is either [1, index, value] for point update or [2, left, right] for range minimum query.

Examples

Example 1:

Input:

nums = [5,2,6,3]
operations = [[2,1,3],[1,2,1],[2,0,3]]

Output:

[2,1]

Explanation:

The minimum on [1,3] is 2. After changing index 2 from 6 to 1, the minimum on the full array becomes 1.

Example 2:

Input:

nums = [7,4,9,2,8]
operations = [[2,0,4],[1,3,10],[2,1,4]]

Output:

[2,4]

Explanation:

The first query sees 2 as the smallest value. After the update, the range [1,4] has minimum 4.

Loading...
Range Minimum Query with Point Update