누적 합(Prefix Sum)

누적 합(Prefix Sum)

배열의 처음에서 각 위치까지의 원소의 합을 구한 배열

부분 합, 구간 합이라고도 한다.

 

 

1차원 누적 합

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

11659번: 구간 합 구하기 4

i번째에서 j번째까지의 원소의 합을 일일이 구한다고 해보자. N이 10만이므로, i와 j를 정할 경우의 수는 \(\binom{100000}{2} \)이기에 반드시 시간초과가 날 것이다. 이를 효율적으로 구하는 방법이 누적 합이다.

 

누적 합이란 상기했듯이 배열의 처음에서 각 위치까지의 원소의 합을 구한 배열이다. 따라서 누적 합 배열 psum은 원소를 저장한 배열 arr를 이용해 다음과 같이 정의할 수 있다.  배열의 첫 index가 1이라 가정하면

$$ psum[i] = \sum_{j=1}^{i}arr[j] $$

즉, psum[i]는 arr[1]부터 arr[i]까지 더한 값이다. 이때 psum[0] = 0인데, 배열의 첫 index가 1이므로 이는 자연스럽다.

 

arr[i]부터 arr[j]까지의 합을 구하는 과정은 간단한데, psum[j] - psum[i-1]이다. 이렇게 하면 \(O(N + M)\) 시간에 답을 구할 수 있다. 특정 구간의 합을 한 번만 구한다면 시간복잡도는 \(O(N)\)이 될 것이다.

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tiii;

int N, M;
ll psum[100001];

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin >> N >> M;
    for (int i{1}; i <= N; i++)
    {
        int n;
        cin >> n;
        psum[i] = psum[i - 1] + n;
    }

    for (int k{1}; k <= M; k++)
    {
        int i, j;
        cin >> i >> j;
        cout << psum[j] - psum[i - 1] << "\n";
    }
}

 

 

2차원 누적 합

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

11660번: 구간 합 구하기 5

원소를 저장한 2차원 배열을 arr라 정의한다면 2차원 누적 합 배열 psum은

$$ psum[i][j] = \sum_{x=1}^{i}\sum_{y=1}^{j}arr[x][y] $$

라 정의할 수 있다.

그렇다면 arr[x1][y1]부터 arr[x2][y2]까지의 누적 합은 어떻게 구하는가?

psum[x1 - 1][y1 - 1] = ①

psum[x2][y1 - 1] = ① + ② 

psum[x1 - 1][y2] = ① + ③

psum[x2][y2] = ① + ② + ③ + ④

우리가 구하고자 하는 arr[x1][y1]부터 arr[x2][y2]까지의 누적 합은 ④이다. 위 네 식에 의해

④ = psum[x2][y2] - psum[x2][y1 - 1] - psum[x1 - 1][y2] + psum[x1 - 1][y1 - 1]이다.

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tiii;

int N, M;
int psum[1025][1025];

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin >> N >> M;
    for (int i{1}; i <= N; i++)
    {
        int sum{0};
        for (int j{1}; j <= N; j++)
        {
            int n;
            cin >> n;
            sum += n;
            psum[i][j] = psum[i - 1][j] + sum;
        }
    }

    for (int i{1}; i <= M; i++)
    {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;

        cout << psum[x2][y2] - psum[x1 - 1][y2] - psum[x2][y1 - 1] + psum[x1 - 1][y1 - 1] << "\n";
    }
}