prefix sum (1) 썸네일형 리스트형 76. Prefix Sum 누적합(Prefix Sum)은 원소의 값이 변하지 않을 때 임의의 연속된 구간에 속한 원소들의 합을 빠르게 구하기 위해 사용되는 방법이다. 아이디어와 구현 모두 간단하며 다양하게 응용할 수 있다. 일반적으로 $1$차원 누적합이 많이 사용되지만 $2$차원 누적합이 사용되는 경우도 존재한다. $3$차원 이상의 누적합은 잘 사용되지 않는다. 길이가 $n$인 $1$차원 배열 $a$가 존재할 때 누적합 $s_i$는 일반적으로 다음과 같이 정의된다.$$s_0 = 0$$$$s_i = a_i+s_{i-1}\ (1 \le i \le n)$$즉 $s_i$는 첫 번째 원소부터 $i$번째 원소까지의 합과 같다. $s_i$를 구했다면 임의의 연속된 구간에 속한 원소들의 합은 다음과 같이 구할 수 있다.$$\sum_{k=l}^r.. 이전 1 다음
