부분 합 솔루션

[1. 개요]

공식

• pSum[i] = A[i] - pSum[i-1]

구간 [a, b] 의 원소들의 합

• sum[a~b] = pSum[b] - pSum[a-1]

a-1 의 원소의 접근해야 할 필요가 있으므로,

구현의 편의 성을 위해 배열은 0이 아닌 1부터 시작하도록 하는 것이 좋다.

• 이러한 개념은 2차원 배열로도 확장 된다.

 

2차원 배열 상에서 부분 합이 살짝 까다로울 수 있다.

단순 넓이 개념으로 생각하면 아래와 같이 구할 수 있다.

 

pSum[y,x] 를 [0,0] ~ [y,x] 내 속한 원소의 합으로 생각하는 것이다.

• link 463 예체 참조, 

---

[2. 예제]

• https://testkernelv2.tistory.com/463
• https://testkernelv2.tistory.com/534
• https://testkernelv2.tistory.com/535
• https://testkernelv2.tistory.com/699
• https://testkernelv2.tistory.com/733
• f
• g