What is prefix sum array?
Prefix Sum array is a data structure design which helps us to answer several queries such as sum in a given range in constant time which would otherwise take linear time. It requires a linear time preprocessing and is widely used due to its simplicity and effectiveness. $^{[1]}$
The application of prefix sum array
Range Sum Query
For example, 303. Range Sum Query - Immutable, in this problem, without prefix array we have to sum the array every time when we call sumRange function.
Referencxe List
[1] https://iq.opengenus.org/prefix-sum-array/
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License. Welcome to reprint, and please indicate the source: Lingjun Meng's Blog Keep the content of the article complete and the above statement information!
