Prefix Sum & Difference Array

Learn the Prefix Sum technique — a powerful range-query optimization that answers range sum queries in O(1) after O(n) preprocessing. Includes dry runs, complexity analysis, common mistakes, and multi-language implementations.

Extend the Prefix Sum technique to two dimensions — efficiently answer rectangular range sum queries on a 2D grid in O(1) after O(m×n) preprocessing. Includes intuition, dry runs, and multi-language implementations.

Learn the Difference Array technique — a complement to Prefix Sum that enables O(1) range updates and O(n) reconstruction. Includes core concepts, dry runs, step-by-step examples, and multi-language implementations.

Curated practice problems for mastering Prefix Sum and Difference Array techniques. Problems are organized by difficulty with hints and approach guidance.