Array Scan

Array scan processes elements sequentially from left to right (or right to left). It forms the basis of many algorithms, including aggregation, filtering, searching, and transformations.

You use it when every element must be inspected at least once.

Problem

Given an array $A$ of length $n$, compute an aggregate value such as:

$$ \sum_{i=0}^{n-1} A[i] $$

or apply a function to each element.

Algorithm

Sequential scan:

scan(A, f, init):
    result = init

    for i from 0 to length(A) - 1:
        result = f(result, A[i])

    return result

Example

Let

$$ A = [8, 3, 5, 1, 9] $$

Compute the sum:

step	element	result
1	8	8
2	3	11
3	5	16
4	1	17
5	9	26

Return:

$$ 26 $$

Correctness

The scan maintains an invariant: after processing index $i$, the variable result contains the aggregate of elements from index $0$ through $i$.

Each iteration updates the result by combining the current value with the next element. After the final iteration, all elements have been processed exactly once, so the result contains the aggregate over the entire array.

Complexity

operation	time
scan	$O(n)$

Space usage:

$$ O(1) $$

for simple aggregates.

When to Use

Array scan is appropriate when:

• every element must be examined
• computing sums, counts, or reductions
• building prefix or cumulative results
• applying transformations in sequence

It is less suitable when:

• only a small subset of elements is needed
• random access queries dominate

Implementation

def scan(a, f, init):
    result = init
    for x in a:
        result = f(result, x)
    return result

func Scan[T any, R any](a []T, init R, f func(R, T) R) R {
    result := init
    for _, x := range a {
        result = f(result, x)
    }
    return result
}