Prefix sum / 누적합, 구간의 합 구하기

N - Slimes /atcoder.jp (https://skysign.tistory.com/170) 문제에서 사용된 알고리즘으로, prefix sum 알고리즘이 있습니다.
prefix sum을 활용하면, 1차원 배열이 있다고 할 때, 1차원 배열의 특정 구간 x ~ y 까지의 합을 빠르게 구할 수 있습니다.

\begin{aligned}
1 \leq n \leq N \\
a_x \in ( a_1 ... a_n ) \\
a_y \in ( a_1 ... a_n ) \\
1 \leq x < y \leq N \\
\end{aligned}

자바 코드는 아래와 같습니다.

long[] as = new long[N+1];
long[] prefixSum = new long[N+1];

for(int i=1; i<=N; ++i) {
    as[i] = sc.nextLong();
    prefixSum[i] = prefixSum[i-1] + as[i];
}

prefix sum을 구했으므로, 위의 x, y 에 해당하는 수의 특정 구간의 합을 구하는 것은 빼기 한번으로 가능합니다.

prefixSum[y] - as[x-1]