Consider the problem of identifying a contiguous subarray of a fixed length k that yields the maximum sum within a given array arr of size n. A direct approach involves iterating over all possible starting indices left from 0 to n-k. For each left, the sum of the subarray arr[left ... left+k-1] is computed. This results in a time complexity of O(k * (n-k+1)), wich is O(n^2) in the worst case (when k ≈ n/2). This is inefficient for large n (e.g., 5000 to 10000) and becomes infeasible for multiple queries.

The primary bottleneck is the repeated summation of overlapping subarrays. This can be optimized by precomputing a prefix sum array, allowing any subarray sum to be retrieved in constent time O(1). The prefix sum array pref is computed such that pref[i] stores the sum of elements from arr[0] to arr[i] inclusive.

Given pref, the sum of elements between indices l and r (inclusive) is calculated as:

sum(l, r) = pref[r] - (l > 0 ? pref[l-1] : 0)

If l == 0, the sum is simply pref[r]. This transformation reduces the time complexity for multiple queries to O(n) for preprocessing and O(1) per query.

Implementation

The following C++ code demonstrates prefix sum construction and usage.

Basic Implementation (Explicit Boundary Check):

#include <iostream>
using namespace std;

int main() {
    const int MAX_SIZE = 1005;
    int sequence[MAX_SIZE];
    int prefix[MAX_SIZE];
    int numElements;

    cin >> numElements;
    for (int idx = 0; idx < numElements; ++idx) {
        cin >> sequence[idx];
    }

    // Compute prefix sums
    for (int idx = 0; idx < numElements; ++idx) {
        if (idx == 0) {
            prefix[idx] = sequence[idx];
        } else {
            prefix[idx] = prefix[idx-1] + sequence[idx];
        }
    }

    // Query examples
    // Sum from index 0 to 4
    int sum_0_to_4 = prefix[4];
    // Sum from index 2 to 5
    int sum_2_to_5 = prefix[5] - prefix[1];

    return 0;
}

Encapsulated Function Approach (Handles l=0 uniformly):

#include <iostream>
using namespace std;

int numElements;
int sequence[1005];
int prefix[1005];

// Helper function to get prefix sum at index, returns 0 for index -1
int getPrefixValue(int index) {
    if (index < 0) return 0;
    return prefix[index];
}

int main() {
    cin >> numElements;
    for (int idx = 0; idx < numElements; ++idx) {
        cin >> sequence[idx];
    }

    // Compute prefix sums
    for (int idx = 0; idx < numElements; ++idx) {
        if (idx == 0) {
            prefix[idx] = sequence[idx];
        } else {
            prefix[idx] = prefix[idx-1] + sequence[idx];
        }
    }

    // Query examples using the helper function
    // Sum from index 0 to 4: getPrefixValue(4) - getPrefixValue(-1)
    int sum_0_to_4 = getPrefixValue(4) - getPrefixValue(-1);
    // Sum from index 2 to 5: getPrefixValue(5) - getPrefixValue(1)
    int sum_2_to_5 = getPrefixValue(5) - getPrefixValue(1);

    return 0;
}

Related Concepts

The prefix technique can be adapted to other associative operations:

• Prefix Product: Stores cumulative products. The product of a subarray arr[l...r] would be pref_product[r] / pref_product[l-1] (handling division by zero appropriately).
• Prefix XOR: Stores cumulative XOR values. The XOR of a subarray arr[l...r] can be computed as pref_xor[r] ^ pref_xor[l-1]. The core principle remains the same: precompute cumulative results to enable fast range queries.