Prefix Sum
* Definition: The prefix sum of an array is a new array where each element represents the sum of all elements in the original array up to that index.
* Example:
* Original array: `[1, 2, 3, 4, 5]`
* Prefix sum array: `[1, 3, 6, 10, 15]`
* `1` is the sum of elements up to index 0 (just the first element).
* `3` is the sum of elements up to index 1 (1 + 2).
* `6` is the sum of elements up to index 2 (1 + 2 + 3) and so on.
Suffix Sum
* Definition: The suffix sum of an array is a new array where each element represents the sum of all elements in the original array from that index to the end.
* Example:
* Original array: `[1, 2, 3, 4, 5]`
* Suffix sum array: `[15, 14, 12, 9, 5]`
* `15` is the sum of elements from index 0 to the end (1 + 2 + 3 + 4 + 5).
* `14` is the sum of elements from index 1 to the end (2 + 3 + 4 + 5).
* `12` is the sum of elements from index 2 to the end (3 + 4 + 5), and so on.
Uses of Prefix and Suffix Sums
* Efficient Range Queries: You can use prefix and suffix sums to quickly calculate the sum of elements within a specific range of an array. For example, to find the sum of elements from index `i` to `j`:
* `prefix_sum[j] - prefix_sum[i - 1]` (for prefix sum)
* `suffix_sum[i] - suffix_sum[j + 1]` (for suffix sum)
* Algorithm Optimization: Prefix and suffix sums can help optimize algorithms that involve repetitive sum calculations, reducing the number of operations required.
Key Points
* Prefix sum is a cumulative sum from the beginning.
* Suffix sum is a cumulative sum from the end.
* They provide a way to pre-process an array for efficient range sum queries.
Let me know if you'd like more elaborate examples or want to explore specific use cases of prefix and suffix sums in algorithms.