📜 WAYPOINT LESSON
Prefix Sums + Binary Search
⭐⭐⭐ advanced⏳ 30 min read📍 Lesson 181 of 281
When the prefix array is monotone, every two-condition subarray count becomes two binary searches — one idea, dozens of problems.
Monotone prefixes unlock counting
Positive values make prefix sums increasing; the subarray (i, j] has sum in [L, R] exactly when P[j]-R <= P[i] <= P[j]-L. Count positions i with two binary searches. If values can be negative, prefixes stop being monotone — the same counting then needs BIT/merge-sort (next lesson).