Glossary: Coding Interviews in Java
Prefix sum
Also written: prefix sums
An array where `prefix[i]` is the total of the first `i` items, so any range total is one subtraction: `prefix[end] - prefix[start]`. Setup is O(n), then each question is O(1).
Glossary: Coding Interviews in Java
Also written: prefix sums
An array where `prefix[i]` is the total of the first `i` items, so any range total is one subtraction: `prefix[end] - prefix[start]`. Setup is O(n), then each question is O(1).