Prefix Sums & Difference Arrays
Prefix Sums
Prefix sums are a simple yet powerful technique used to preprocess an array to allow for efficient range sum queries. The idea is to create an auxiliary array where each element at index i contains the sum of all elements from the start of the original array up to index i.
Documents & Articles
- Competitive Programmer’s Handbook – Chapter 9 (CSES)
- The Incarnadine Trai ning Units – Prefix Sums
- USACO Guide - Prefix Sums
- USACO Guide - More on Prefix Sums
- Prefix Sum of Matrix (Or 2D Array) - GeeksforGeeks
Videos
Difference Arrays
Difference arrays are a related technique that allows for efficient range updates on an array. Instead of updating each element in a range directly, we update the difference array, which can then be used to reconstruct the original array with all updates applied.
Documents & Articles
- 1D Difference Array - GeeksforGeeks
- An Introduction to Difference Arrays - Codeforces
- Two Dimensional Difference Array - GeeksforGeeks