• Home
  • Learn
  • Feed
  • Ladder
  • Saved
← Roadmapsall 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