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