Skip to content
CCC Python Course

Prefix sums (1D, 2D, prefix/suffix max)

Stage
4
Module
M4.3
Lessons
1

In this module

  • Build a prefix sum array to answer range-sum queries in O(1) time.
  • Use prefix/suffix max arrays to find the best value in a range.
  • Extend prefix sums to 2D grids for rectangular range queries.
  • Recognize when preprocessing trades setup time for faster queries.

Before this module

M1.8Lists (1D and 2D)M2.9Complexity analysis and deriving the target from N

Lessons

  1. 1Prefix sums

Practice

Try these on the judge. Each link opens the problem on DMOJ.

  1. 2017 S1
    Sum Game (opens on DMOJ in a new tab) DMOJ

    Track a running total as you scan, and use it to answer a question about the whole range.

    Why DMOJ: A direct running-total problem, the same idea as this lesson's prefix sum array.

  2. 2018 J3
    Are we there yet? (opens on DMOJ in a new tab) DMOJ

    Use cumulative totals across a table to answer a positional question.

    Why DMOJ: A cumulative-sum problem solved the same way as this lesson's range-sum queries.