# Array Scan

# 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:

```id="array-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

```python id="array-scan-python"
def scan(a, f, init):
    result = init
    for x in a:
        result = f(result, x)
    return result
```

```go id="array-scan-go"
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
}
```