Problem 663: Sums of Subarrays

Mathematical Foundation

Theorem 1 (Kadane, 1984). The maximum contiguous subarray sum of an array $A[0..n-1]$ equals

where $P_k = \sum_{j=0}^{k-1} A[j]$ is the $k$-th prefix sum, with $P_0 = 0$.

Proof. Any contiguous subarray sum $\sum_{j=p}^{q} A[j] = P_{q+1} - P_p$. Maximizing over $0 \leq p \leq q < n$ is equivalent to maximizing $P_b - P_a$ over $0 \leq a < b \leq n$. Since we also allow the empty subarray (sum 0), the result follows. $\square$

Theorem 2 (Segment Tree for Maximum Subarray Sum). A segment tree on the prefix sum array $P_0, P_1, \ldots, P_n$ supports:

• Point update of $A[k]$ (which is a suffix update on $P$) in $O(\log n)$ time.
• Global maximum subarray sum query in $O(1)$ time.

Each node for interval $[l, r]$ stores the tuple $(\max P, \min P, \text{max\_sub}, \text{total})$.

Proof. We prove correctness of the merge operation. Consider a node $v$ with children $L = [l, m]$ and $R = [m+1, r]$. The maximum subarray sum within $v$‘s interval is $\max_{l \leq a < b \leq r}(P_b - P_a)$, which equals the maximum of three cases:

1. Both $a, b \in [l, m]$: this is $\text{max\_sub}(L)$.
2. Both $a, b \in [m+1, r]$: this is $\text{max\_sub}(R)$.
3. $a \in [l, m]$ and $b \in [m+1, r]$: this is $\max_{b \in R} P_b - \min_{a \in L} P_a = \text{max\_prefix}(R) - \text{min\_prefix}(L)$.

Taking the maximum of these three cases gives $\text{max\_sub}(v)$.

For the prefix aggregates:

A point update $A[k] \mathrel{+}= \delta$ changes $P_j$ by $\delta$ for all $j > k$. This is a suffix update on the prefix sum array, handled by updating the segment tree along the path from leaf $k+1$ to the root. With lazy propagation for the suffix-add, each update costs $O(\log n)$. $\square$

Lemma 1 (Non-negativity). If $M_n(i) < 0$ is possible only when all $A[j] < 0$, but by convention the maximum subarray sum is at least 0 (empty subarray).

Proof. The empty subarray has sum 0, so $M_n(i) \geq 0$ always. $\square$

Editorial

Maintain maximum subarray sum under point updates using a segment tree. S(n, l) = sum of max subarray sums after each of l updates. We suffix-update P[k+1..n] by delta.

Pseudocode

    A = array of n zeros
    P = prefix sum array of n+1 zeros
    build segment tree T on P[0..n]
    total = 0
    For i from 1 to l:
        k = t[2i-2] mod n
        delta = 2 * (t[2i-1] mod n) - n + 1
        A[k] += delta
        suffix-update P[k+1..n] by delta
        update T at positions k+1 through n by +delta
        M = T.root.max_sub
        total += max(0, M)
    Return total

Complexity Analysis

• Time: $O(n + l \log n)$ — building the segment tree takes $O(n)$; each of the $l$ updates and queries takes $O(\log n)$.
• Space: $O(n)$ for the segment tree.

For the target parameters: $n \approx 10^7$, $l = 200{,}000$ updates, giving approximately $200{,}000 \times 23 \approx 4.6 \times 10^6$ operations.

Answer

#include <bits/stdc++.h>
using namespace std;

/*
 * Problem 663: Sums of Subarrays
 *
 * Maintain maximum subarray sum under point updates.
 * S(n, l) = sum of max subarray sums after each of l updates.
 *
 * Uses segment tree with nodes storing:
 *   (max_prefix, min_prefix, total, max_subarray_sum)
 * Point update: O(log n), query: O(1).
 */

struct Node {
    long long max_prefix, min_prefix, total, max_sub;
};

Node merge(const Node& L, const Node& R) {
    return {
        max(L.max_prefix, L.total + R.max_prefix),
        min(L.min_prefix, L.total + R.min_prefix),
        L.total + R.total,
        max({L.max_sub, R.max_sub, L.total + R.max_prefix - L.min_prefix})
    };
}

class SegTree {
    int n;
    vector<Node> tree;
public:
    SegTree(int n) : n(n), tree(4 * n, {0, 0, 0, 0}) {}

    void update(int pos, long long delta, int node = 1, int lo = 0, int hi = -1) {
        if (hi == -1) hi = n - 1;
        if (lo == hi) {
            tree[node].total += delta;
            tree[node].max_prefix = max(0LL, tree[node].total);
            tree[node].min_prefix = min(0LL, tree[node].total);
            tree[node].max_sub = max(0LL, tree[node].total);
            return;
        }
        int mid = (lo + hi) / 2;
        if (pos <= mid) update(pos, delta, 2*node, lo, mid);
        else update(pos, delta, 2*node+1, mid+1, hi);
        tree[node] = merge(tree[2*node], tree[2*node+1]);
    }

    long long query() { return max(0LL, tree[1].max_sub); }
};

int main() {
    // Small verification
    int n = 50;
    SegTree seg(n);

    // Kadane's verification
    vector<int> A = {1, -2, 3, -1, 2};
    long long kadane_max = 0, cur = 0;
    for (int x : A) {
        cur = max(0LL, cur + x);
        kadane_max = max(kadane_max, cur);
    }
    printf("Kadane's on [1,-2,3,-1,2] = %lld (expected 4)\n", kadane_max);
    assert(kadane_max == 4);

    printf("Segment tree implementation ready for Problem 663.\n");
    printf("Full solution requires the exact pseudo-random generator.\n");

    return 0;
}

"""
Problem 663: Sums of Subarrays

Maintain maximum subarray sum under point updates using a segment tree.
S(n, l) = sum of max subarray sums after each of l updates.
"""

class SegTree:
    """Segment tree for maximum subarray sum queries."""

    def __init__(self, n):
        self.n = n
        self.size = 1
        while self.size < n + 1:
            self.size *= 2
        # Each node: (max_prefix, min_prefix, total, max_subarray)
        self.tree = [(0, 0, 0, 0)] * (2 * self.size)

    def _merge(self, left, right):
        lmax_p, lmin_p, ltotal, lmax_s = left
        rmax_p, rmin_p, rtotal, rmax_s = right
        total = ltotal + rtotal
        max_p = max(lmax_p, ltotal + rmax_p)
        min_p = min(lmin_p, ltotal + rmin_p)
        max_s = max(lmax_s, rmax_s, ltotal + rmax_p - lmin_p)
        return (max_p, min_p, total, max_s)

    def update(self, pos, delta):
        """Add delta to position pos."""
        pos += self.size
        cur = self.tree[pos]
        new_val = cur[2] + delta
        self.tree[pos] = (max(0, new_val), min(0, new_val), new_val, max(0, new_val))
        pos >>= 1
        while pos >= 1:
            self.tree[pos] = self._merge(self.tree[2*pos], self.tree[2*pos+1])
            pos >>= 1

    def query(self):
        """Return maximum subarray sum."""
        return max(0, self.tree[1][3])

def solve_small(n, l):
    """Solve S(n, l) using segment tree."""
    # Pseudo-random generator (from problem: t_0 = 0, t_{i+1} = t_i^2 mod something)
    # Actually the problem uses a specific generator. For verification,
    # we use the values from the problem statement.
    # The generator: s_0 = 290797, s_{i+1} = s_i^2 mod 50515093
    # t_i = s_i mod 2^20 (or similar)

    # Using the standard PE663 generator:
    s = 290797
    def next_s():
        nonlocal s
        s = (s * s) % 50515093
        return s

    A = [0] * n
    seg = SegTree(n)

    total = 0
    for i in range(1, l + 1):
        t1 = next_s()
        t2 = next_s()
        k = t1 % n
        delta = 2 * (t2 % n) - n + 1
        A[k] += delta
        seg.update(k, delta)
        M = seg.query()
        total += M

    return total

# Test with small cases
# Note: the exact generator may differ from what's assumed here.
# The verification values would need the exact generator from the problem.
print("Problem 663: Sums of Subarrays")
print("Implementation uses segment tree for O(log n) per update")

# Demonstrate Kadane's algorithm
def kadane(arr):
    """Maximum subarray sum via Kadane's algorithm."""
    max_ending = 0
    max_so_far = 0
    for x in arr:
        max_ending = max(0, max_ending + x)
        max_so_far = max(max_so_far, max_ending)
    return max_so_far

# Example from problem
A = [0, 0, 0, 0, 0]
print(f"Initial: A = {A}, M = {kadane(A)}")

# Verify Kadane's on known arrays
assert kadane([1, -2, 3, -1, 2]) == 4  # subarray [3, -1, 2]
assert kadane([-1, -2, -3]) == 0  # empty subarray
assert kadane([5, -2, 3]) == 6  # [5, -2, 3]
print("Kadane's algorithm verified.")