[Algorithm] Pregix Sum (누적합, 구간합)

누적합, 구간합

• 배열의 일부 구간에 대한 합을 빠르게 구할 수 있음
• N개의 원소의 합을 구하는 경우
  • 완전 탐색으로 구하면 O(N)
  • 구간합으로 구하면 O(1)

 

1차원 배열

• sum이라는 리스트를 만들어서 sum[i]에 arr[0] ~ arr[i-1] 의 합을 저장
  
  • 0 부터 i 까지의 합을 구하고 싶은 경우 : sum[i+1]
  • i 부터 j 까지의 합을 구하고 싶은 경우 : sum[j+1] - sum[i]

 

2차원 배열

• sum이라는 리스트를 만들어서 sum[i][j]에 arr[0][0] ~ arr[i-1][j-1] 의 합을 저장
  • (0, 0) 부터 (i, j) 까지의 합을 구하고 싶은 경우 : sum[i+1][j+1]

• sum 리스트를 만드는 방법?

# arr는 n*n 배열
# 1. 행단위로 더하고 열단위로 더하기 -> n*n 반복문을 2번 돌려야함
# 2. 
sum = [[0 for _ in range(n+1)] for _ in range(n+1)]

for i in range(1, n+1):
	for j in range(1, n+1):
    	sum[i][j] = arr[i-1][j-1] + sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1]