aloalgoPrefix & Suffix Arrays
Prefix arrays precompute cumulative information from the start, while suffix arrays do the same from the end. They transform O(n) range queries into O(1) lookups after O(n) preprocessing.Prefix Sum
The most common prefix array. prefix[i] stores the sum of elements from index 0 to i-1.Why prefix[0] = 0?
Having prefix[0] = 0 simplifies the range sum formula. Without it, you'd need special handling for ranges starting at index 0.Common Prefix Sum Problems
Subarray Sum Equals K
Product of Array Except Self
Prefix Max/Min
Instead of sums, track the maximum or minimum seen so far.2D Prefix Sum
Extend prefix sums to matrices for O(1) rectangular region queries.Suffix Arrays
Same concept but computed from right to left. Useful when you need information about elements to the right.When to Use Prefix/Suffix Arrays
- Multiple range queries: Precompute once, query many times in O(1).
- Finding subarrays with target sum: Use prefix sum + hash map.
- Product except self: Combine prefix and suffix products.
- Trapped water / stock problems: Need max/min from both directions.
- Matrix region sums: Use 2D prefix sum.
Time & Space Complexity
- Build prefix array: O(n) time, O(n) space
- Range query: O(1) time
- 2D prefix: O(m×n) build, O(1) query
Was this helpful?
Company
Practice
© 2026 aloalgo. All rights reserved.