구간합
-
Prefix sum / 누적합, 구간의 합 구하기카테고리 없음 2020. 1. 21. 11:12
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