구간합 개념 및 관련 문제 모음!

구간합이란 합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘

합 배열의 정의

S[i] = A[0] + A[1] + A[2] +.... + A[i-1] + A[i]
-> A[0]부터 A[i] 사이의 합을 구하기

위에서 A[i]부터 A[j]까지의 배열 합을 합 배열 없이 구하는 경우, 최악의 경우는 i가 0이고 j가 N인 경우이므로 이떄 시간복잡도는 O(N)
-> 하지만 합배열을 사용하면 O(1)안에 답을 구할 수 있음

합 배열을 만드는 공식

S[i] = S[i-1] + A[i]

구간 합을 구하는 공식

S[j] - S[i-1] -> i부터 j까지 구간의 합

이때 배열의 값이 자주 바뀐다면, 구간합 알고리즘이 아닌 세그먼트 트리의 개념을 사용하게 됨!

---

문제 1

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

구간합 구하기 기본 문제
-> 핵심은 index 0자리에 0 그대로 두기

문제 2

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

2차원 표에 채워져 있는 값의 구간합 구하기

2차원 배열 누적 합 계산 방식은 익숙해지자...ㅠㅠ

구간합 [i][j] 값을 채우는 구간 합 채우기 및 답 구하기 예시

		for(int i = 1; i <= N; i++){
            for(int j = 1; j <= N; j++){
                sumArr[i][j] = sumArr[i-1][j] + sumArr[i][j-1] - sumArr[i-1][j-1] + A[i][j];
            }
        }

        for(int i = 0; i < M; i++){
            st = new StringTokenizer(br.readLine());
            int x1 = Integer.parseInt(st.nextToken());
            int y1 = Integer.parseInt(st.nextToken());
            int x2 = Integer.parseInt(st.nextToken());
            int y2 = Integer.parseInt(st.nextToken());

            int result = sumArr[x2][y2] - sumArr[x1-1][y2] - sumArr[x2][y1-1] + sumArr[x1-1][y1-1];
            System.out.println(result);
        }

문제 3

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

위 문제 핵심 아이디어

(A+B) % C는 ((A % C) + (B % C)) % C와 같다
-> 특정 구간 수들의 나머지 연산을 더해 나머지 연산을 한 값과, 이 구간의 합의 나머지 연산을 한 값이 같다

구간합 배열을 이용한 S[i] - S[j]는 원본 배열의 j+1부터 i까지의 구간 합이다

S[i] % M의 값과 S[j] % M의 값이 같다면 (S[i] - S[j]) % M은 0이다
-> 즉 구간합 배열의 원소를 M으로 나눈 상태로 업데이트하고 S[i]와 S[j]가 같은 (i,j)쌍을 찾으면 원본 배열에서 j+1부터 i까지의 구간합이 M으로 나누어 떨어지는 것을 알 수 있음

1. A 배열의 합 배열 S 생성
   1,2,3,1,2 -> 1,3,6,7,9

2. 힙 배열의 S의 모든 값을 M으로 나눈 나머지 연산 수행
   1,3,6,7,9 -> 1,0,0,1,0

3. 변경된 합 배열에서 원소 값이 0인 개수만 세어 정답에 더함
   0: 3개, 원소값이 0이라는 것은 원본 배열에 0부터 i까지의 구간합 이 이미 M으로 나누어 떨어진다는 뜻

4.이제 나머지 값이 같은 합 배열의 갯수를 셈, 변경된 합 배열에서 원소의 값이 같은 2개의 원소를 뽑는 모든 경우의 수를 구하여 정답에 더하면 됨
-> 위 경우엔 0이 3개 이므로 3C1, 1이 2개이므로 2C2
-> 결과는 3+3+1

---