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.sql

.mode list
.headers off
CREATE TABLE arr(idx INTEGER PRIMARY KEY, val INTEGER);
INSERT INTO arr(idx, val) VALUES
  (0, 3), (1, 1), (2, 4), (3, 1), (4, 5), (5, 9), (6, 2), (7, 6);
WITH RECURSIVE walk(idx, total) AS (
  SELECT 0, 0
  UNION ALL
  SELECT walk.idx + 1, walk.total + arr.val
  FROM walk JOIN arr ON arr.idx = walk.idx
)
SELECT total FROM walk WHERE idx = (SELECT COUNT(*) FROM arr);

trace.sql

.mode list
.headers off
CREATE TABLE arr(idx INTEGER PRIMARY KEY, val INTEGER);
INSERT INTO arr(idx, val) VALUES
  (0, 3), (1, 1), (2, 4), (3, 1), (4, 5), (5, 9), (6, 2), (7, 6);
WITH RECURSIVE walk(step, before_total, val, total) AS (
  SELECT 1, 0, arr.val, arr.val FROM arr WHERE arr.idx = 0
  UNION ALL
  SELECT walk.step + 1, walk.total, arr.val, walk.total + arr.val
  FROM walk JOIN arr ON arr.idx = walk.step
)
SELECT line FROM (
  SELECT step AS k,
         'step ' || (step - 1) || ': arr(' || (step - 1) || ')='
         || val || ' total ' || before_total || ' -> ' || total AS line
  FROM walk
  UNION ALL
  SELECT 999, 'final total = ' || total FROM walk
  WHERE step = (SELECT COUNT(*) FROM arr)
)
ORDER BY k;

Complexity

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

Implementation notes

SQL: the array is modeled as a two-column table arr(idx INTEGER PRIMARY KEY, val INTEGER) so the loop index is the table's primary key and a WITH RECURSIVE CTE can step through the rows one at a time. SELECT SUM(val) FROM arr would jump straight to 31 without the running update the lesson is teaching, so the recursive CTE visits indices 0..7 explicitly and carries (idx, total) forward.
The CTE seed SELECT 0, 0 produces the empty-prefix invariant; the recursive arm joins walk to arr on arr.idx = walk.idx to read the current element, increments the index, and adds the value.
The final SELECT total FROM walk WHERE idx = (SELECT COUNT(*) FROM arr) picks the row produced after the last addition. SQLite emits 31 under .mode list with no headers, so the output is stable across releases.
trace.sql reuses the same WITH RECURSIVE shape but carries (step, before_total, val, total) so each frame prints step i: arr(i)=V total B -> T. The final line prints the canonical final total = 31 summary.

linear scan Visit each element exactly once in index order.

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