Maximum Subarray Sum Query with Point Update

Given an array nums, support point updates and queries for the maximum subarray sum inside a requested interval. For every query, return the best subarray sum within that range. This is a classic advanced segment tree problem where each node stores total sum, prefix sum, suffix sum, and best answer.

Input Format

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

Output Format

maximum subarray sum 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 maximum subarray sum query.

Examples

Example 1:

Input:

nums = [1,-2,3,4,-1]
operations = [[2,0,4],[1,1,5],[2,0,4]]

Output:

[7,12]

Explanation:

Before the update, the best subarray is 3+4=7. After changing -2 to 5, the whole array [1,5,3,4,-1] has best subarray sum 12.

Example 2:

Input:

nums = [-1,-2,-3]
operations = [[2,0,2],[1,1,4],[2,0,2]]

Output:

[-1,4]

Explanation:

With all negatives, the best subarray is the largest single element. After updating one element to 4, the best subarray becomes 4.

Loading...
Maximum Subarray Sum Query with Point Update