Contiguous range-sum questions and repeated queries over a stable sequence.
- contiguous subarray
- range sum
- sum ending at this index
prefix is the exact sum from index 0 through the current index.
O(n) preprocessing or scan. Typical auxiliary space: O(1) to O(n), depending on stored history.
JAVA STARTING POINT
A template to adapt, not memorize.
long prefix = 0;
for (int value : values) {
prefix += value;
// Compare or store this prefix state.
}Common mistakes
- Missing the empty prefix at index -1
- Using int when sums may overflow
- Applying a positive-only window to negative values
PUBLISHED / 03
Learn in this order.
Available articles always appear before the publishing plan.
Prefix Sum in Java: A Beginner's Guide to Range Sums and Subarray Patterns
Learn prefix sums from scratch with visual examples, Java code, recognition clues, common subarray patterns, and mistakes to avoid.
Read article →Subarray Sum Equals K in Java: From Brute Force to Prefix Sum
Count subarrays with sum K using a prefix sum and frequency map, with beginner-friendly diagrams, a dry run, Java solutions, and common mistakes.
Read article →Longest Subarray with Sum K
Use prefix sums and earliest indexes to handle positive and negative values in linear time.
Read article →PLANNED PRACTICE
What comes after the published lessons.
- Range sum queryPlanned, not yet published
