Cumulative sum

2 snippets across 2 stacks — Interview Prep, SQL

DSAInterview Prep

Prefix Sum

syntax

Build a cumulative sum array so any range sum can be computed in O(1).
prefix[i] = sum of arr[0..i-1]
Range sum [l..r] = prefix[r+1] - prefix[l]

example

// JavaScript
function buildPrefix(arr) {
  const prefix = [0];
  for (const val of arr) {
    prefix.push(prefix[prefix.length - 1] + val);
  }
  return prefix;
}
function rangeSum(prefix, left, right) {
  return prefix[right + 1] - prefix[left];
}

# Python
def build_prefix(arr):
    prefix = [0]
    for val in arr:
        prefix.append(prefix[-1] + val)
    return prefix

def range_sum(prefix, left, right):
    return prefix[right + 1] - prefix[left]

output

arr=[3,1,4,1,5] → prefix=[0,3,4,8,9,14]
rangeSum(1,3) = prefix[4]-prefix[1] = 9-3 = 6

Note Build: O(n) time, O(n) space. Query: O(1). Extremely useful when you need many range sum queries. Variant: prefix XOR for range XOR problems. For 2D grids, use 2D prefix sums with inclusion-exclusion.

SQLSQL

SUM / AVG OVER (Running Totals)

SQL · Window Functions

syntax

SUM(column) OVER (ORDER BY column ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW)

example

SELECT
  order_date,
  total_amount,
  SUM(total_amount) OVER (ORDER BY order_date) AS running_total,
  AVG(total_amount) OVER (
    ORDER BY order_date
    ROWS BETWEEN 2 PRECEDING AND CURRENT ROW
  ) AS moving_avg_3
FROM orders
WHERE user_id = 42;

output

-- order_date  | total_amount | running_total | moving_avg_3
-- 2025-09-01  | 150.00       | 150.00        | 150.00
-- 2025-10-05  | 230.00       | 380.00        | 190.00
-- 2025-11-12  | 180.00       | 560.00        | 186.67

Note Without ROWS/RANGE, the default frame is RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW, which includes all rows with the same ORDER BY value. Use ROWS for exact row-based windows. This distinction matters when ORDER BY has ties.