누적합, 구현, 그래프이론, DFS, BFS, 트리순회, 완탐, 백트래킹, 비트마스킹, 그리디, 라인스위핑, 투포인터, LIS, 이분탐색, DP, 최단거리, 펜윅트리

위 순서대로 알고리즘을 방식을 학습합니다.

누적합(Prefix Sum)

배열의 일부 구간에 대한 합을 빠르게 구할 수 있느 스킬입니다.

N개의 원소로 이루어진 배열이 주어질때, 반복문을 통해 부분 배열의 합을 구하려면 O(n)이 거리는데 부분합을 이용하면 모든 부분합을 O(1)에 바로 구할 수 있습니다

1차원 배열

array을 순차 탐색하면서 sum 배열을 만들어주면 된다.

sum[i]에는 arr[0] + arr[1] + .. + arr[i-1]정보가 담겨있다고 생각하면 된다.

S(i, j) = sum[j+1] - sum[i]

2차원 배열

2차원도 배열도 같다.

sum[i][j]에는 arr[0][0]부터 arr[i-1][j-1] 까지의 합이 담겨 있습니다.

2차원 구간 합을 어떻게 구하나면 상수 시간에 구간합을 구할 수 있게 된다.

arr의 (x1, y1)부터 (x2, y2)까지 합을 S라 할때,

S = sum[x2+1][y2+1] - sum[x1] [y2+1] - sum[x2+1][y1] + sum[x1][y1]

구할 수 있다.