Prefix Sum

Master prefix sum techniques for range queries, subarray problems, and matrix operations. Learn 1D, 2D, hash map combinations, and difference arrays.

The Prefix Sum technique transforms $O (N^{2})$ range query problems into $O (1)$ lookups by preprocessing cumulative sums. Master 1D and 2D prefix sums, hash map combinations for subarray problems, difference arrays for range updates, and variants like prefix XOR and product. Learn when to use prefix sum vs sliding window and how to avoid common off-by-one errors.

Featured Guide

Complete Guide

The Complete Prefix Sum Guide: Master All Patterns, Templates, and Techniques

The ultimate comprehensive guide to prefix sum. Learn all variants (1D, 2D, hash map combinations), when to use each pattern, complete templates in multiple languages, and a systematic approach to solve any prefix sum problem.

25 min read

Interactive Tool

Roadmap

Prefix Sum Visualizer

Master prefix sum algorithms interactively. Build intuition for 1D arrays, range queries, and hash map optimizations. Watch how cumulative sums are built and queried in real-time.

Prefix Sum Learning Roadmap: From Beginner to Interview-Ready in 6 Weeks

A structured 6-week learning path to master all prefix sum patterns. Progress from basic 1D sums to advanced 2D matrices, hash maps, and difference arrays with curated problems and milestones.

Tutorials

Why Your Prefix Sum Has Off-by-One Errors (And How to Fix Them)

Off-by-one errors are the #1 reason prefix sum solutions fail. Learn why they happen, the prefix[0] = 0 trick, the correct range formula, and how to avoid indexing mistakes forever.

Prefix SumOff-by-One ErrorsCommon Mistakes

8 min

The {0: 1} Initialization: Why It's Critical for Subarray Sum

Missing the {0: 1} initialization is why your subarray sum solution fails test cases. Learn why this base case is critical, when to use {0: 1} vs {0: -1}, and how to never forget it again.

Prefix SumHash MapCommon Mistakes

9 min

2D Prefix Sum Off-by-One: The Inclusion-Exclusion Mistake

Off-by-one errors in 2D prefix sum are even trickier than 1D. Learn the inclusion-exclusion formula, why we add and subtract specific cells, and how to avoid indexing mistakes in matrix queries.

Prefix Sum2D MatrixOff-by-One Errors

9 min

When Prefix Sum Fails: Problems That Look Like Prefix Sum But Aren't

Not every subarray problem needs prefix sum. Learn when to use Kadane's algorithm, sliding window, or other techniques instead.

Prefix SumKadane's AlgorithmSliding Window

6 min

Debugging Subarray Sum: Why Your Prefix Sum + Hash Map Fails

Your subarray sum solution passes some test cases but fails others. Learn the step-by-step debugging process, common bugs, and how to trace through examples to find the issue.

Prefix SumHash MapDebugging

10 min

Prefix Sum with Negative Numbers: Why Sliding Window Breaks

Negative numbers break sliding window but work perfectly with prefix sum + hash map. Learn why and how to handle them correctly.

Prefix SumNegative NumbersEdge Cases

5 min

Prefix Sum Edge Cases: Empty Arrays, Single Elements, and All Zeros

Your solution passes examples but fails edge cases. Learn the comprehensive edge case checklist for prefix sum problems.

Prefix SumEdge CasesTesting

5 min

Difference Array Mistakes: Why Your Range Updates Fail

Your difference array solution looks correct but fails test cases. Learn the 4 common bugs, why forgetting the final prefix sum step breaks everything, and how to debug range update problems.

Prefix SumDifference ArrayCommon Mistakes

9 min

Prefix Product Pitfalls: Handling Zeros and Division

Zeros break naive prefix product solutions. Learn why division fails, how to use prefix/suffix products, and the correct approach for Product of Array Except Self.

Prefix SumProductEdge Cases

8 min

Prefix Sum vs Hash Map: When You Need Both (And When You Don't)

Confused about when to combine prefix sum with hash maps? Learn when each technique is sufficient alone vs when they must work together.

Prefix SumHash MapPattern Selection

5 min

Prefix Sum Pattern Recognition: Spot It in 10 Seconds

Learn to identify prefix sum problems instantly with keyword triggers, problem patterns, and a fast decision framework for interviews.

Prefix SumPattern RecognitionInterview Strategy

5 min

Prefix Sum Complexity Analysis: When O(n) Space is Worth It

Learn when the O(n) space cost of prefix sum is justified, how to analyze time/space tradeoffs, and how to explain your choices in interviews.

Prefix SumComplexity AnalysisInterview Strategy

6 min

1D Prefix Sum Template: Range Sum Queries in O(1) Time

Master the fundamental 1D prefix sum pattern with production-ready templates in Python, JavaScript, and Java. Learn when to use it, how to handle edge cases, and avoid common mistakes.

Prefix SumRange Queries1D Array

12 min

Prefix Sum + Hash Map: Solve Subarray Sum Problems in O(n)

Master the powerful combination of prefix sum and hash maps to solve subarray sum problems in linear time. Learn the technique, templates in three languages, and when to use this pattern.

Prefix SumHash MapSubarray Sum

15 min

2D Prefix Sum: Matrix Range Queries in O(1) Time

Master 2D prefix sum for matrix range queries. Learn the inclusion-exclusion principle, templates in three languages, and how to avoid off-by-one errors in 2D indexing.

Prefix Sum2D MatrixRange Queries

14 min

Difference Array: Range Updates in O(1) with Prefix Sum

Master the difference array technique—the inverse of prefix sum. Learn how to perform multiple range updates in O(1) each, complete templates, and when to use this powerful pattern.

Prefix SumDifference ArrayRange Updates

13 min

Prefix Sum vs Sliding Window: When to Use Each Pattern

Confused about when to use prefix sum vs sliding window? Learn the clear decision framework, side-by-side comparisons, and examples of when each pattern is optimal.

Prefix SumSliding WindowPattern Comparison

11 min

Prefix XOR and Prefix Product: Beyond Prefix Sum

Extend prefix sum logic to XOR and product operations. Learn when to use prefix XOR, how to handle prefix products with zeros, and templates for non-additive cumulative operations.

Prefix SumXORProduct

12 min