Array Sum (Linear Scan)

Walk an array once, accumulating each element into a running total. This is the canonical single-pass linear scan and the simplest possible loop invariant: after step i, total equals the sum of arr[0..i].

Algorithm

Trace Output

basic.cpp

#include <iostream>
#include <vector>

int main() {
    std::vector<int> arr = {3, 1, 4, 1, 5, 9, 2, 6};
    int total = 0;
    for (size_t i = 0; i < arr.size(); ++i) {
        total = total + arr[i];
    }
    std::cout << total << std::endl;
    return 0;
}

trace.cpp

#include <iostream>
#include <vector>

int main() {
    std::vector<int> arr = {3, 1, 4, 1, 5, 9, 2, 6};
    int total = 0;
    for (size_t i = 0; i < arr.size(); ++i) {
        int before = total;
        total = total + arr[i];
        std::cout << "step " << i << ": arr[" << i << "]=" << arr[i]
                  << " total " << before << " -> " << total << std::endl;
    }
    std::cout << "final total = " << total << std::endl;
    return 0;
}

Complexity

Time: O(n)
Space: O(1)

Implementation notes

C++: use the explicit for (size_t i = 0; i < arr.size(); ++i) loop and int total. Calling std::accumulate(arr.begin(), arr.end(), 0) would hide the iteration the lesson is teaching.
std::vector<int> documents the integer-array contract; the unsigned size_t for i matches the container's size() return type.
The replay shows i, arr[i], and total before and after each addition, matching the lesson spec's state-transition table.

linear scan Visit each element exactly once in index order.

running total `total` accumulates the sum as the loop advances.