파이썬 - 누적합

누적합은 1차원이나 2차원 배열을 주고 일정한 범위에 속한 원소의 합을 구하는 개념이다.

반복문으로 풀었을때의 시간복잡도를 줄여줄 수 있다.

1차원 배열

https://www.acmicpc.net/problem/11659

import sys

N,M= map(int,input().split())

N_list = list(map(int,sys.stdin.readline().split()))
sum_list = [0]

for i in N_list:
    elem = i + sum_list[-1]
    sum_list.append(elem)


for i in range(M):
    start,end = map(int,input().split())

    ans = sum_list[end]-sum_list[start-1]

    print(ans)

1차원 배열에서의 누적합, 부분합은 간단하다.

배열을 반복하며 누적합 배열을 만들어주고

부분합은 누적합의 차이를 이용한다.

예를 들면 3번째에서 5번째 원소의 합을 구해야된다면 누적합배열에서 5번째 원소까지의 누적합과 2번쨰 원소까지의 누적합을 찾아서 빼준 것이 3~5번째의 누적합이다.

2차원 배열

2차원 배열에서의 누적합도 누적합 배열을 만들어서 한다.

https://www.acmicpc.net/problem/11660

import sys

input = sys.stdin.readline

N,M = map(int,input().split())

graph = []

sum_list = [[ 0 for _ in range(N+1)] for _ in range(N+1)]

for i in range(N):

    graph_line = list(map(int,input().split()))

    graph.append(graph_line)

for i in range(1,N+1):
    for j in range(1,N+1):
        sum_list[i][j] = graph[i-1][j-1] + sum_list[i-1][j] + sum_list[i][j-1] - sum_list[i-1][j-1]


for i in range(M):

    x1,y1,x2,y2 = map(int,input().split())

    ans = sum_list[x2][y2] - sum_list[x1-1][y2] - sum_list[x2][y1-1] + sum_list[x1-1][y1-1]

    print(ans)

아래의 그림에서 (3,3)인 7까지의 누적합을 구한다고 생각해보자

(3,3)까지의 누적합은 파란색 칸인 (3,2)까지의 누적합과 노란색 칸인 (2,3)까지의 누적합과 (3,3) 본인 좌표인 7을 더해준 것과 같다.

그런데 초록색 네모 부분인 (2,2)까지의 누적합은 두번 더해졌으므로 이 부분을 한번 빼준다.

이걸 식으로 표현하면 아래와 같다.

sum_list[i][j] = graph[i-1][j-1] + sum_list[i-1][j] + sum_list[i][j-1] - sum_list[i-1][j-1]

마찬가지로 부분합도 비슷한 방식으로 구할 수 있다.

아래의 그림에서 노란 부분의 누적합을 구한다고 해보자

해당 부분의 누적합은 (3,3)까지의 누적합에서 보라색 칸까지의 누적합을 빼주고, 초록색 부분은 두번 빠졌으므로 한번 더해주는 식으로 구할 수 있다.

이걸 식으로 표현하면

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

이렇게 표현할 수 있다.

문제별로 인덱스의 시작점이 0,1로 다 다르니 인덱스를 주의하면서 구해야한다.