Lesson 5: Prefix Sums

Computing range sum queries in constant time over a fixed 1D array.

Open reading material (PDF)

PassingCars

Count the number of passing cars on the road

Difficulty Level: Easy

CountDiv

Compute number of integers divisible by k in range [a..b].

Difficulty Level: Medium

GenomicRangeQuery

Find the minimal nucleotide from a range of sequence DNA.

Difficulty Level: Medium

MinAvgTwoSlice

Find the minimal average of any slice containing at least two elements.

Difficulty Level: Medium