Prefix Sums
You know knapsack patterns. Now you need a tool that speeds up range computations. Prefix sums turn O(n) range queries into O(1).
Lessons
1. Intro
The Goal
2. The Range Sum Problem
Why we need this
3. Naive Approach
Loop every query
4. Vocabulary - Prefix Sum
The definition
5. Building the Prefix Array
One pass
6. Answering Range Queries
The formula
7. Prefix Sums - Implementation
The code
8. Prefix Sums - Walkthrough
Tracing the algorithm
9. Challenge: Off-by-One Errors
Getting indices right
10. Quiz: Prefix Sums Basics
Knowledge check
11. Static Range Sum Queries - Problem Statement
Query range sums fast
12. Static Range Sum Queries - Why Prefix Sums
Applying the technique
13. Codeforces 869B Kuriyama Mirai's Stones - Problem Statement
Two prefix arrays
14. Static Range Sum Queries - The Formula
Prefix[r] - prefix[l-1]
15. Codeforces 869B Kuriyama Mirai's Stones - Two Arrays
Sorted and original
16. Static Range Sum Queries - Walkthrough
Applying prefix sums
17. Codeforces 869B Kuriyama Mirai's Stones - Walkthrough
Two array variant
18. Quiz: Range Query Complexity
Understanding the tradeoff
19. Static Range Sum Queries - Implementation
Complete solution
20. Codeforces 869B Kuriyama Mirai's Stones - Implementation
The code
21. LeetCode 560 Subarray Sum Equals K - Problem Statement
HashMap prefix counting
22. LeetCode 560 Subarray Sum Equals K - HashMap Trick
Count with frequency
23. LeetCode 560 Subarray Sum Equals K - Implementation
The code
24. LeetCode 560 Subarray Sum Equals K - Walkthrough
HashMap technique trace
25. Challenge: Subarray Sum Zero
Special case of k=0
26. Quiz: Prefix Sum + HashMap
Knowledge check
27. LeetCode 238 Product of Array Except Self - Problem Statement
Prefix and suffix products
28. LeetCode 238 Product of Array Except Self - Prefix and Suffix
Two directions
29. LeetCode 238 Product of Array Except Self - Walkthrough
Prefix and suffix products
30. Quiz: Product Edge Cases
Handling zeros
31. LeetCode 238 Product of Array Except Self - Space Optimization
One output array
32. LeetCode 304 Range Sum Query 2D - Problem Statement
2D prefix sum queries
33. LeetCode 304 Range Sum Query 2D - The Concept
Inclusion-exclusion
34. LeetCode 304 Range Sum Query 2D - Walkthrough
2D prefix sums trace
35. Challenge: 2D Submatrix Count
Counting with target sum
36. LeetCode 304 Range Sum Query 2D - Implementation
The code
37. Quiz: 2D Prefix Sums
Knowledge check
38. LeetCode 53 Maximum Subarray Sum - Problem Statement
Kadane connection
39. LeetCode 53 Maximum Subarray Sum - Implementation
Kadane's algorithm
40. Quiz: Kadane vs Prefix
Comparing approaches
41. Lessons from Prefix Sums
summary
42. Pattern - When to Use Prefix Sums
Recognizing the pattern
43. What's Next
Preview of LIS
44. Section Recap
What we learned
Practice Problems
Prefix sum DP - teaches how to precompute and reuse subproblem results
Classic 2D prefix sum problem with constant-time rectangle queries.
Standard prefix sum + hashmap pattern used everywhere.
Handles negative numbers with prefix sum + hashmap technique.
Teaches prefix sum optimization to reduce O(NK²) to O(NK).
Demonstrates when greedy+recursion outperforms pure recursion
Combines 2D prefix sums with hashmap for matrix subarray counting.
Covered with full walkthrough in this section.
Covered with full walkthrough in this section.
Covered with full walkthrough in this section.
Covered with full walkthrough in this section.
Arrange tiles to maximize prime prefix sums. Teaches creative use of prefix sums with number theory.
Reverse engineer a sorted sequence from partial prefix sums. Tests deep understanding of prefix sum properties.
Minimize operations to make a prefix sum the global minimum. Combines greedy with prefix sum analysis.
Count maximal prefix sums across all permutations. Beautiful combinatorics with prefix sums.
Find subarray with sum divisible by k. Classic prefix sum + modular arithmetic + hashmap pattern.
Count subarrays divisible by k. Prefix sum with modular counting - interview favorite.
Longest subarray with equal 0s and 1s. Transform to prefix sum problem with hashmap.
Count subarrays where sum equals length. Prefix sum + hashmap counting pattern.
Count valid triangles with prefix sums. Transforms geometry to array problem.
Count alternating substrings with wildcards. Prefix counting with state tracking.
Maximize wins in RPS with prefix sums. Sliding window + prefix optimization.
Connect forests without creating cycles. DSU with prefix optimization.
Count inversions with merge sort. Classic divide and conquer application.
Simple usage of prefix sum
2D DP with prefix sums combining multiple DP techniques