[Python] 구간 합

구간 합

합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘

• 주어진 수열에서 임의의 구간에 포함된 요소의 합을 빠르게 구하는 방법
• 앞에서부터 합을 누적하여 미리 계산해 저장해 놓고 활용하는 방법

1차원 구간 합 구하기

1. 값 입력 받기
2. 값 배열 생성하기
3. 합 배열 생성하기 >> 누적합

   📢 Point
   index 0에 0이 없으면 index out of range이 됨.
   j - (i-1) 이나 (j-1) - (j-2)를 할 때 계산을 위해 dummy index(value)가 필요함.

4. 구간 합 구하기

sum[j] - sum[i-1] # i ~ j 구간의 합

2차원 구간 합 구하기

1. 값 입력 받기
2. 값 배열 생성하기
3. 합 배열 생성하기 >> 누적합

   📢 Point
   합 배열을 생성하고 계산하기 위해서 (1, N), (N, 1)은 모두 0으로 채워서 생성. 0이 없으면 index out of range

4. 구간 합 구하기

   📢 Point
   포함하지 않는 row, col 값을 빼야 하는데, 둘 다 빼면 중복하여 계산된 부분이 있어 더해줘야 함.

# (x1, y1) ~ (y1, y2) 구간의 합
sum_arr[x2][y2] - sum_arr[x2][y1-1] - sum_arr[x1-1][y2] + sum_arr[x1-1][y1-1]