IntevalSum.py

# 03-2 구간 합
# 합 배열을 이용하여 시간 복잡도를 줄이기 위해 사용한다.

# 1. 설명
# S를 구간합 배열이라고 하자.
# 그럼 S[i]는 1번째부터 i번째까지의 합을 의미한다.
# 따라서 다음 요소 S[i+1] = S[i] + A[i]로 쉽게 구할 수 있다.

# 이를 좀 더 응용하여, i ~ j까지 합을 구해보자.
# intevalSum = S[j] - S[i-1] 으로 특정 구간에 해당하는 요소들의 합도 구할 수 있다.

# 2. 시간 복잡도
# 구간 합의 시간 알고리즘은 O(n)에 속한다.


# 3. 응용: 2차원 리스트에서 구간 합 배열
# 다음과 같이 2차원 리스트가 주어졌다고 가정하자.
# 이때 1행과 1열을 0으로 채우는 이유는 구간 합을 구할 때, 인덱스가 1부터 시작하자고 정했기 때문이다.
# 0 0 0 0 0
# 0 1 2 3 4
# 0 2 3 4 5
# 0 3 4 5 6

# 먼저 2차원 리스트의 구간 합 2차원 리스트D를 만들어보자
# D[i][j] = D[i-1][j] + D[i][j-1] - D[i-1][j-1] + A[i][j]

# 이를 이용하여 2차원 리스트의 구간 합을 구해보자.

# 구간은 X1 Y1 X2 Y2 이런 식으로 주어진다.
# (x1, y1) ~ (x2, y2)까지의 합을 구해보자.
# D[x2][y2] - D[x1-1][y2] - D[x2][y1-1] + D[x1-1][y1-1]로 구할 수 있다.