Skip to main content

Prefix Sum (Range Query)

Learn Prefix Sum (Range Query) (Range Query Techniques, Advanced DSA) with worked examples, diagrams and interview questions. Free on JavaSchoolLab.

Range Sum Queries with Prefix Sums A range query asks for something about a slice of an array, such as the sum of a[l..r] . Adding the slice each time costs O(n) per query. Build a prefix array once, where prefix[i] is the sum of the first i elements, and every query becomes prefix[r+1] - prefix[l] in O(1) . Building costs O(n). It works for sums, counts and XOR, but the array must not change between queries.

More lessons in Range Query Techniques