1. 구간합 (Prefix Sum)
1) 기존 배열 -> 누적합(합배열) : (주어진 배열의 합 배열을 전부 구해놓을 것)
2) 누적합(합배열) 더하거나 빼서 -> 구간 합
특징
합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘
2. 과정 Process
1. 합 배열 구하기 : 리스트 A가 있을 때 합 배열 S는 다음과 같이 정의
• S[i] = A[0] + A[1] + A[2] + .... + A[i]
• 기존의 리스트 데이터들을 전처리한 배열
• 합 배열을 미리 구해 놓으면 기존 리스트의 일정 범위의 합을 구하는 시간 복잡도가 O(N)->O(1)
• S[i] = S[i-1] + A[i] : 1차원 배열 or temp += i으로 놓고 S.append(temp)하기
• D[i][j] = D[i-1][j] + D[i][j-1] - D[i-1][j-1] +A[i][j] : 2차원 배열
2. 구간 합을 구하는 공식
• S[j] - S[i-1] : i에서 j까지의 구간 합
• D[x2][y2]-D[x2][y1-1]-D[x1-1][y2]+D[x1-1][y1-1] : (x1,y1) ~(x2,y2)까지의 구간합
3. 작동 방식
• 주어진 배열 array의 모든 index에 대하여 합 배열 구하기 by S[i] = S[i-1] + A[i]
• 미리 만들어놓은 합 배열 -> 구간 합 바로 구하기 by S[j] - S[i-1] : i에서 j까지의 구간 합
• index 번호 = i번째 수 : 맞추기 위해 합 배열의 [0]은 임의의 값 집어넣기 (list의 크기를 +1)
• 합 배열 구하기 전의 기존 리스트 A는 크기 n으로 해도 상관없음
• 1차원 리스트 초기화시 : [0] * (n+1)
• 2차원 리스트 초기화시 : [[0]*(n+1) for _ in range(n+1)]
• 2차원 구간 합 배열 : (0,0) ~ (X,Y) 까지의 합 배열
