Your free access ends in 7 days — and you haven’t tried it yet. Watch one algorithm run, start to finish. It takes about two minutes.

Try one problem
0
Concept

Overview

Precompute running totals · range sum in O(1)
step 1 / 13
3
1
4
1
5
9
2
[0][1][2][3][4][5][6]
prefix P (P[0] = 0)
0
·
·
·
·
·
·
·
[0][1][2][3][4][5][6][7]
Concept
▸
1given arr (n elements)
2P = array of size n+1
3P[0] = 0                      // sum of nothing
4for i in 0..n−1:
5    P[i+1] = P[i] + arr[i]
6// now P is ready
7rangeSum(l, r):
8    return P[r+1] − P[l]      // O(1)
state
  • n7

line 1A prefix-sum array answers "what is the sum of arr[0..i]?" instantly. Precompute it ONCE, then any range sum becomes a single subtraction. The trick that turns repeated range queries from O(n) each into O(1) each.