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.