Easy · Prefix Sum
Understand → Visualise → Practice.
If you need the sum of many different ranges of the same array, add things up once and reuse the work.
prefix[i] holds the sum of the first i values. The sum of nums[l..r] is prefix[r + 1] − prefix[l].
prefix[0] = 0.
prefix[i + 1] = prefix[i] + nums[i].
sum(l..r) = prefix[r + 1] − prefix[l].
O(n) to build, O(1) per query. Summing each range directly is O(n) per query.
Use a prefix array one longer than nums so the empty prefix (0) has its own slot.
Read the full guides first: Big-O and Complexity, Arrays and Dynamic Arrays, Prefix Sums and Difference Arrays.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.