Module: 접두사 합계

약간의 배열이 있습니다. 변경 사항이 없으면 이 배열의 하위 세그먼트에서 일부 함수의 값을 빠르게(한 줄보다 빠르게) 찾을 수 있습니다. 이를 위해서는 추가 메모리를 사용하고 사전 계산을 수행해야 합니다.
예를 들어 배열의 일부 세그먼트에서 합계를 빠르게 찾아야 합니다.
인덱스 i가 i보다 작거나 같은 인덱스를 가진 배열의 모든 요소의 합이 되는 접두사 합계의 배열을 얻습니다.
a[] – 주어진 배열, p[] – 접두사 합계의 배열


어레이 카운트 p:
분명히 p[0] = a[0]입니다. p[i – 를 통해 p[i]를 쉽게 다시 계산할 수 있습니다. 1] 때문에 i 접두사의 금액은 i 접두사의 금액 – 1 + a[i].
따라서 접두사 합계를 계산하는 코드는 다음과 같습니다.

정수 a[n], p[n];
p[0] = a[0< /스팬>];
for (int i = 1; i < n; i++)
         p[i] = p[i -  1] + a[i];