2. Arrays & Hashing

Prefix sums

0 of 5 activities0%

Reading 1

Sum of a[l..r] in O(1)

Open

prefix[i] = a[0] + ... + a[i-1] (one common convention: prefix[0]=0, prefix[i] = sum of first i elements).

Then sum from l to r inclusive is prefix[r+1] - prefix[l].

Build once in O(n), answer many range-sum queries quickly.

// prefix[0]=0
// prefix[i] = a[0]+...+a[i-1]
long long sumLR = prefix[r+1] - prefix[l];

Check 2

Open

Prefix sums help most when you need

Fill in 3

Open

Try it 4

Open

Print prefix values.

main.cpp

Loading editor…

Program input (stdin)

Output will appear here.

Assignment 5

Open

Read n, then n ints, then l r (0-based inclusive). Print sum a[l]+...+a[r].

main.cpp

Loading editor…