[자료구조] 구간 합

📚 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]까지의 구간 합

문제 풀이

백준 11660번: 구간 합 구하기 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

백준 10986번: 나머지 합

• 핵심 아이디어
  • (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