Prefix Sum: How to Quickly Calculate Interval Sum Using Prefix Sum Array?

The prefix sum array is an auxiliary array used to quickly calculate the sum of intervals. It is defined as follows: for the original array A, the prefix sum array S has S[0] = 0, and for k ≥ 1, S[k] is the sum of elements from A[1] to A[k], i.e., S[k] = S[k-1] + A[k]. For example, if the original array A = [1, 2, 3, 4, 5], its prefix sum array S = [0, 1, 3, 6, 10, 15]. The core formula for calculating the sum of an interval is: the sum of elements from the i-th to the j-th element of the original array is S[j] - S[i-1]. For example, to calculate the sum of A[2] to A[4], we use S[4] - S[1] = 10 - 1 = 9, which gives the correct result. The advantages include: preprocessing the S array takes O(n) time, and each interval sum query only takes O(1) time, resulting in an overall complexity of O(n + q) (where q is the number of queries), which is much faster than the O(qn) complexity of direct calculation. It should be noted that index alignment (e.g., adjusting the formula if the original array starts from 0), interval validity, and the space-for-time tradeoff are important considerations. The prefix sum array is implemented through "pre-accumulation".