SyntaxShelf

Cumulative sum

2 snippets across 2 stacks - Interview Prep, SQL

DSAInterview Prep

Prefix Sum

DSA · Arrays & Strings
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.

Frequently asked questions

How does Interview Prep handle cumulative sum?
This task is covered in 2 stacks on this page: Interview Prep, SQL. The "Prefix Sum" snippet in Interview Prep uses `Build a cumulative sum array so any range sum can be computed in O(1).`.
Which code does the Interview Prep example use?
The "Prefix Sum" snippet uses `Build a cumulative sum array so any range sum can be computed in O(1).`, from the Arrays & Strings section of the Interview Prep cheat sheet.
Which stacks cover "cumulative sum" on this page?
Interview Prep, SQL. Together they hold 2 copy-ready snippets for this task.
Is there anything to watch out for?
Yes. For "Prefix Sum": 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.

Browse all tasks by intent