- create an array <code>prefix</code> where <code>prefix[i]</code> is the sum of all elements up to index $i$ > [!NOTE] Prefix Naming Convention > Subarrays that start at index 0 are referred to as "prefixes" of the array. Prefix sums refer to the respective sums of each prefix. - prefix sums enable you to find the sum of **any** subarray in $O(1)$ - i.e to find sum of subarray from $i$ to $j$, we can just do - <code>prefix[j] - prefix[i - 1]</code> - OR: <code>prefix[j] - prefix[i] + nums[i]</code> - (this alternate avoids the out of bound case when i = 0) ![[prefix sum.png]] ``` Given an array nums, prefix = [nums[0]] for (int i = 1; i < nums.length; i++) prefix.append(nums[i] + prefix[prefix.length - 1]) ``` - prefix sum is a great tool when problem involves sums of a subarray - costs only $O(n)$ space complexity to build, but enables all future subarray query runtimes to be $O(1)$ - prefix sum is a form of **pre-processing**, which is when you store pre-computed data in a data structure before running the main logic of your algorithm - can often improve complexity of your algorithm