Detailed Explanation of Segment Tree Interval Maximum Subarray Sum Query and Update Operations

Detailed Explanation of Segment Tree Interval Maximum Subarray Sum Query and Update Operations

Problem Description

Given an array \(arr\) of length \(n\), we wish to efficiently support the following two operations:

  1. Query Operation: Query the maximum subarray sum (i.e., the sum of the contiguous subarray with the largest sum) of any interval \([l, r]\).
  2. Update Operation: Modify the value at a specific position \(i\) to \(val\).

The goal is to implement a data structure that minimizes the time complexity for both operations (typically aiming for \(O(\log n)\) level).

Background Knowledge

This is a classic advanced application problem of segment trees. Ordinary interval sum queries cannot directly yield the maximum subarray sum because the maximum subarray may span both left and right sub-intervals.
To complete queries and updates within \(O(\log n)\) time, we need to maintain four values in each node of the segment tree and compute the parent node's value through a merging strategy.

Solution Process

Step 1: Understand the Properties of "Maximum Subarray Sum"

For an interval, its maximum subarray sum (denoted as mx) can originate from three possibilities:

  1. Entirely within the left sub-interval.
  2. Entirely within the right sub-interval.
  3. Spanning across the left and right sub-intervals (i.e., the maximum suffix sum of the left sub-interval + the maximum prefix sum of the right sub-interval).

To calculate the spanning case, we also need to know for each interval:

  • Interval Sum (sum): The sum of all elements in the interval.
  • Maximum Prefix Sum (pre): The maximum contiguous sum starting from the left endpoint of the interval.
  • Maximum Suffix Sum (suf): The maximum contiguous sum ending at the right endpoint of the interval.

Step 2: Define the Segment Tree Node Structure

Each node (corresponding to an interval) stores four values:

class Node:
    def __init__(self):
        self.sum = 0   # Interval sum
        self.pre = 0   # Maximum prefix sum
        self.suf = 0   # Maximum suffix sum
        self.mx = 0    # Maximum subarray sum

Step 3: Merge Two Sub-intervals to Obtain the Parent Interval

Assuming the left child node is left and the right child node is right, the parent node res is calculated as follows:

  • Interval Sum: res.sum = left.sum + right.sum
  • Maximum Prefix Sum: res.pre = max(left.pre, left.sum + right.pre)
    (Either use only the left part, or extend into the right part)
  • Maximum Suffix Sum: res.suf = max(right.suf, right.sum + left.suf)
  • Maximum Subarray Sum: res.mx = max(left.mx, right.mx, left.suf + right.pre)
    (Take the maximum of the three cases)

Example:
Array [3, -1, 2, 4]
Left sub-interval [3, -1]: sum=2, pre=3, suf=2, mx=3 (subarray [3])
Right sub-interval [2, 4]: sum=6, pre=6, suf=6, mx=6 (subarray [2,4])
After merging:

  • sum = 2+6=8
  • pre = max(3, 2+6)=max(3,8)=8
  • suf = max(6, 6+2)=max(6,8)=8
  • mx = max(3, 6, 2+6)=max(3,6,8)=8 (corresponding to the sum of subarray [3,-1,2,4])

Step 4: Build Tree (Initialization)

  1. Recursively split the array into halves until reaching leaf nodes.
  2. Leaf node: sum=pre=suf=mx=arr[i] (If empty subarrays are allowed, negative numbers need consideration, but typically the maximum subarray sum must include at least one element, so directly take this value).
  3. Merge child node information from bottom to top.

Time Complexity: \(O(n)\), each node is calculated once.

Step 5: Point Update

  1. Recursively traverse from the root to the target leaf node and update its value.
  2. Re-merge the four values for all nodes along the path during backtracking.

Time Complexity: \(O(\log n)\), only one path is updated.

Step 6: Interval Query

The query interval may span multiple nodes, requiring the merging of multiple nodes' information:

  1. If the current node's interval is completely within the query interval, directly return the node's four values.
  2. If it lies entirely on one side, recurse on that side.
  3. If it spans both left and right, query both sides separately, then merge the two results (using the same merging method as in Step 3).

Note: A temporary node is needed to store the merged result.

Example Illustration

Array: arr = [1, -3, 5, 2]
After building the tree, the root node represents interval [0,3]:

  • Left sub-interval [0,1] (values [1,-3]): sum=-2, pre=1, suf=-2, mx=1
  • Right sub-interval [2,3] (values [5,2]): sum=7, pre=7, suf=7, mx=7
  • After merging:
    • sum = -2+7=5
    • pre = max(1, -2+7)=max(1,5)=5
    • suf = max(7, 7+(-2))=max(7,5)=7
    • mx = max(1, 7, (-2)+7)=max(1,7,5)=7 (corresponding to subarray [5,2])
      The maximum subarray sum is 7, corresponding to the right sub-interval's [5,2]. Correct.

Query interval [0,2] (values [1,-3,5]):

  • Left sub-interval [0,1] as above: sum=-2, pre=1, suf=-2, mx=1
  • Right sub-interval [2,2] (leaf 5): sum=5, pre=5, suf=5, mx=5
  • After merging:
    • sum=3
    • pre = max(1, -2+5)=max(1,3)=3
    • suf = max(5, 5+(-2))=max(5,3)=5
    • mx = max(1, 5, (-2)+5)=max(1,5,3)=5
      The result 5 corresponds to subarray [5] (actually, the maximum contiguous sum in [1,-3,5] is 5).

Summary

By maintaining the four values sum, pre, suf, mx, the segment tree can handle interval maximum subarray sum queries and point updates within \(O(\log n)\) time. This is a classic example of using segment trees to solve complex interval merging problems.