Prefix Sums & Difference Arrays

1D and 2D prefix sums, difference arrays for range updates, and prefix XOR and counts.

0 / 5 solved

Question Tags Difficulty Success

1. Both Ends Of The Range

prefix-sumrange-query +2

Medium —

2. Borrowed Query Convention

prefix-sumhalf-open-range +2

Medium —

3. Three Ranges One Pass

difference-arrayrange-update +2

Medium —

4. Four Corners One Rectangle

prefix-sum2d-prefix-sum +2

Medium —

5. The Missing Empty Prefix

prefix-sumhash-map +2

Medium —

Learning Resources

USACO Guide, Prefix Sums

Competitive Programmer's Handbook, Chapter 9, Range queries

CSES Problem Set, Range query problems

Up next

5 of 5 questions here are still unsolved.

Next in Sorting & Searching Comparison Sorts & The n log n Bound