Skip to content
AITroveRead. Build. Understand.
Reading list
Make this comfortable

Maximum-subarray segment trees: preserve the crossing burst

Last updated: 5 Oct 20269 min read
tutorial
IntermediateBy AITrove Editorial

A maximum-subarray segment tree summarizes each nonempty interval by four values: its total sum, greatest nonempty prefix sum, greatest nonempty suffix sum, and greatest nonempty contiguous subarray sum. When adjacent summaries join, the best interval is either inside the left child, inside the right child, or crosses their boundary as the left suffix plus the right prefix. The prefix and suffix also account for an entire neighboring child. This four-field join is associative for consecutive intervals, which permits ordinary segment-tree range decomposition. A point replacement rebuilds only its ancestors. The model scores nonempty fault bursts; a zero-length range is invalid, and a wholly negative range returns its least-negative single score rather than zero.

Operational case

For fault scores [-8,47,-19,61,-83,29,37], the largest contiguous score over the whole feed is 89 from [47,-19,61]. Within [4,7), the best is 66 from [29,37]. Correcting position four from -83 to -17 changes the whole-feed best to 138, because one longer stretch now crosses the old break. A plain range-sum tree would report totals but could not distinguish the crossing candidate. Returning a zero summary for a non-overlapping query branch would also be wrong: zero would invent an empty subarray in a contract that forbids one.

Working Python program

python
from dataclasses import dataclass


@dataclass(frozen=True)
class BurstSummary:
    total: int
    prefix: int
    suffix: int
    best: int


def combine(left, right):
    if left is None:
        return right
    if right is None:
        return left
    return BurstSummary(
        left.total + right.total,
        max(left.prefix, left.total + right.prefix),
        max(right.suffix, right.total + left.suffix),
        max(left.best, right.best, left.suffix + right.prefix),
    )


class FaultBurstIndex:
    def __init__(self, fault_scores):
        if not fault_scores:
            raise ValueError("at least one score is required")
        self.length = len(fault_scores)
        self.tree = [None] * (4 * self.length)

        def build(node, low, high):
            if high - low == 1:
                score = fault_scores[low]
                self.tree[node] = BurstSummary(score, score, score, score)
                return
            middle = (low + high) // 2
            build(node * 2, low, middle)
            build(node * 2 + 1, middle, high)
            self.tree[node] = combine(self.tree[node * 2], self.tree[node * 2 + 1])

        build(1, 0, self.length)

    def replace(self, position, score):
        if not 0 <= position < self.length:
            raise IndexError(position)

        def change(node, low, high):
            if high - low == 1:
                self.tree[node] = BurstSummary(score, score, score, score)
                return
            middle = (low + high) // 2
            if position < middle:
                change(node * 2, low, middle)
            else:
                change(node * 2 + 1, middle, high)
            self.tree[node] = combine(self.tree[node * 2], self.tree[node * 2 + 1])

        change(1, 0, self.length)

    def best_burst(self, left, right):
        if not 0 <= left < right <= self.length:
            raise IndexError("a nonempty range is required")

        def read(node, low, high):
            if right <= low or high <= left:
                return None
            if left <= low and high <= right:
                return self.tree[node]
            middle = (low + high) // 2
            return combine(read(node * 2, low, middle), read(node * 2 + 1, middle, high))

        return read(1, 0, self.length).best


fault_scores = [-8, 47, -19, 61, -83, 29, 37]
burst_index = FaultBurstIndex(fault_scores)
print(burst_index.best_burst(0, 7))
print(burst_index.best_burst(4, 7))
burst_index.replace(4, -17)
print(burst_index.best_burst(0, 7))

Output

Output
89
66
138

Time, space, and tradeoff

Building all summaries costs O(N) time and space for N scores. A replacement and a nonempty range query each touch O(log N) nodes, with O(1) work per join. Recursive calls use O(log N) stack space. The summary stores sums, not the winning endpoint positions; retaining endpoints requires a tie rule and additional fields. It does not support a constant-time arbitrary range addition: changing every value can change the winning interval in a way four old numbers cannot repair. For one fixed array with no updates, a direct scan may be simpler; repeated bounded queries or corrections justify the index.

Common Mistakes

  • Do not treat a zero summary as identity when the winning subarray must be nonempty.
  • Do not omit the suffix-plus-prefix crossing case.
  • Do not call the best total a range sum; it may exclude endpoints.
  • Do not assume these four fields support lazy range addition.

Connected lessons

Compare this operation boundary with Persistent subarray ranks: subtract prefix frequency trees, Li Chao interval offers: limit each line to its valid minutes, All-one frequency buckets: increment, decrement, and read both extremes, Patricia binary routing: compress chains without losing prefix matches, then complete the audit project and decision quiz.

data structures
range-query-structures
Storage details