[자료구조] 구간 합
📚 Do it! 알고리즘 코딩테스트 (c++편)
구간합
구간 합의 핵심 이론
먼저 합 배열을 구해야 한다
S[i] = A[0] + A[1] + A[2] + … + A[i-1] + A[i] // A[0]부터 A[i]까지의 합
합 배열 = 기존의 배열을 전처리한 배열
합 배열을 미리 구해놓으면 기존 배열의 일정 범위의 합을 구하는 시간 복잡도 = O(N) → O(1)
합 배열 S를 만드는 공식 (누적합)
S[i] = S[i-1] + A[i]
구간 합을 구하는 공식
S[j] - S[i-1]
ex) S[5] = A[0] + A[1] + A[2] + A[3] + A[4] + A[5]
S[1] = A[0] + A[1]
S[5] - S[1] = A[2] + A[3] + A[4] + A[5] //A[2]부터 A[5]까지의 구간 합
문제 풀이
- 2차원 구간 합 배열 문제
-
D[i][j]의 값을 채우는 구간 합 공식
D[i][j] = D[i][j-1] + D[i-1][j] + A[i][j] - D[i-1][j-1]
-
x1, y1, x2, y2에 대한 답을 구간 합으로 구하는 방법
D[x2][y2] - D[x1-1][y2] - D[x2][y1-1] + D[x1-1][y1-1]
https://github.com/KimGyeongLock/CodingTest/blob/main/11660.cpp
- 핵심 아이디어
- (A + B) % C == ((A % C) + (B % C)) % C
- 구간 합 배열을 이용한 식 S[j] - S[i]으로
(S[j] - S[i]) % M = 0
을 구하고자 한다. - S[j]와 S[i]가 값이 같다면
S[j] - S[i]) % M = 0
이고 S[j]%M
의 값과S[i]%M
의 값이 같아도S[j] - S[i]) % M = 0
이다.
https://github.com/KimGyeongLock/CodingTest/blob/main/10986.cpp