← Roadmaps all prefix sums problems

➕

Prefix Sums

Cumulative sums, range queries, and difference arrays.

5 stops · 49 problems0/48 on the path done

next ▸ Submatrix Sum QueriesSilver · 1150

1

Range queries

0/16you are here

Answer many [l,r] sum / submatrix queries fast.

○Submatrix Sum Queries ○Range Sum Query Batch ○Ones In Range Lookups ○Range Sum Queries ○Difference Array Builder ○Range XOR Lookups ○Range Addition 2D ○Range Add Point Lookup ○Region Sum With Updates ○Max Square Side Under Threshold ○Maximum Sum Rectangle ○Count Corner Rectangles ○Submatrix Sum Lookups ○Count Submatrices With All Ones ○Grid Rectangle Updates ○Max Sum Rectangle No Larger Than K

2

Difference arrays

0/1

Apply range updates, then read the final array.

○Corporate Flight Bookings

3

Subarray counting

0/16 of 17

Count subarrays with a target property.

○Equal Row and Column Sums ○Equal Sum Split Count ○Even Sum Subarray Count ○Subarrays Summing to K ○Shortest Subarray Reaching Target ○Longest Zero Sum Span ○Continuous Subarray Multiple of K ○Count Square Submatrices Summing to Target ○Subarrays Divisible by K ○Longest Balanced Binary Span ○Zero Sum Subarray Count ○Submatrices Summing to Target ○Subarrays with Bounded Maximum ○Count Subarrays Divisible By K ○Subarrays With K Odds ○Max Size Subarray Sum Equals K +1 in the arena

4

Running aggregates

0/13

Prefix running totals, balances, drawdowns.

○Minimum Value to Stay Positive ○Pivot Index ○Find the Middle Index ○Minimum Prefix Sum Value ○Positive Prefix Count ○First Negative Balance ○Peak Prefix Sum Index ○Equilibrium Index List ○Distinct Prefix Sum Count ○Equilibrium Indices ○Prefix Average Crossing ○Maximum Running Drawdown ○Product of Array Except Self

5

More Prefix Sums

0/2

Everything else built on cumulative sums.

○Count Negative Numbers ○Best Fixed Window Sum

🏁Finish line