1차원 구간 합 (Immutable)

누적 합 $S$ 정의

구간 합 $A[L, R]$ 정의

• $S[0] = 0$ 으로 두면, $L$이 $0$일 때 음수 인덱스 방지할 수 있어 인덱스 관리가 편함.

• 합뿐만 아니라 곱셈이나 XOR 연산도 유사하게 동작할 수 있습니다. 하지만 곱셈의 경우 값이 커지므로 모듈러 연산이 필요합니다.

  $\prod_{k=L}^{R} A[k] = \frac{S[R+1]}{S[L]}$

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N, M; cin >> N >> M;
    vector<int> prefixSum(N + 1, 0);
    for (int i = 0; i < N; i++) {
        int v; cin >> v;
        prefixSum[i + 1] = prefixSum[i] + v;
    }

    while(M--) {
        int i, j; cin >> i >> j; // i와 j는 1부터 시작하므로, (j + 1) (i) -> (j) (i - 1)
        cout << prefixSum[j] - prefixSum[i - 1] << "\n";
    }
}

2차원 구간 합 (Immutable)

2차원 누적 합 $S$ 정의

• $S[i][j]$는 좌상단 $(0,0)$부터 $(i-1,j-1)$까지의 부분 합
  

2차원 구간 합 $A[L, R]$ 정의

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N, M; cin >> N >> M;
    vector<vector<int>> prefixSum(N + 1, vector<int>(N + 1, 0));
    
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            int v; cin >> v;
            prefixSum[i + 1][j + 1] = prefixSum[i + 1][j] + prefixSum[i][j + 1] 
                                        - prefixSum[i][j] + v;
        }
    }

    while(M--) {
        int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2; // x1, y1, x2, y2는 1부터 시작
        cout << prefixSum[x2][y2] - prefixSum[x2][y1 - 1] - prefixSum[x1 - 1][y2] + prefixSum[x1 - 1][y1 - 1] << "\n";
    }
}