[ 백준 11658 ] 구간합 구하기3 (C++)

백준의 구간합 구하기3(11658) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

구간 합을 구해야 하는 문제인데, 단순 1차원 배열이 아닌 2차원 배열 상에서의 구간합을 구해야 하는 문제이다.

단순히 맵을 만들어서 합을 구해야 하는 연산이 주어질 때 마다 직접 구한다면, 최악의 경우 1024x1024x100000 번의 탐색을 해야 하고, 굉장히 오랜 시간이 걸리기 때문에 제 시간에 문제를 해결할 수 없다.

따라서, 본인은 '구간에 대한 연산'을 빠르게 처리할 수 있는 '펜윅트리'를 이용해서 구현하였다. '세그먼트트리'를 이용해도 되지만, 2차원 배열에서의 구간에 대한 연산을 어떻게 적용할지 잘 모르겠어서 '펜윅트리'를 이용해서 구현해보았다.

아직 펜윅트리에 대해서 잘 모른다면 아래의 글을 읽고 오도록 하자.

[ 펜윅트리(Fenwick Tree) 알아보기(Click) ]

위의 글은 1차원 배열에서의 구간에 대한 연산을 펜윅트리에서 진행하는 법에 대해서 설명되어있다. 그럼 이제 이것을 문제에 맞게 2차원으로 옮겨보자.

2차원 펜윅트리를 구현하는 방법은 1차원과 굉장히 비슷하다. 1차원에서는 단순히 하나의 Index에 대해서 연산을 진행했다면, 2차원 펜윅트리에서는 (x좌표 , y좌표) 이렇게 2개의 Index가 한 쌍으로 존재하기 때문에 이 2개의 Index에 대해서 연산을 진행해 주면 된다. 1차원과의 차이를 코드로 보면서 알아보자.

먼저, 단순 Update하는 과정을 보자. 1차원 펜윅트리에서는, 하나의 Index를 특정 'Value'라는 값으로 Update하과 싶을 때, 비트 연산을 이용해서 "해당 Index의 변화로 인해서, 영향을 미치는 Index들을 찾아갔다".

void Update(int Idx, int Value)
{
    while (Idx < Fenwick_Tree.size())
    {
        Fenwick_Tree[Idx] = Fenwick_Tree[Idx] + Value;
        Idx = Idx + (Idx & -Idx);
    }
}

위와 같이 구현하는데, 이를 2차원으로 바꾸면 다음과 같이 구현할 수 있다.

void Update(int x, int y, ll Value)
{
    while (x < N + 1)
    {
        int Temp_y = y;
        while (Temp_y < N + 1)
        {
            FenwickTree[x][Temp_y] = FenwickTree[x][Temp_y] + Value;
            Temp_y = Temp_y + (Temp_y & -Temp_y);
        }
        x = x + (x & -x);
    }
}

위와 같이, (x, y)라는 좌표를 Value로 바꾸고 싶다면, 해당 y축에 의해서 영향을 받는 Index들, 그리고 그 이후에는 x축에 의해서 영향을 받은 Index들을 모두 Update시켜 주면 된다. 실제 Query를 구하는 부분도 동일하게 구현할 수 있다.

ll Query(int x, int y)
{
    ll Result = 0;
    while (x > 0)
    {
        int Temp_y = y;
        while (Temp_y > 0)
        {
            Result = Result + FenwickTree[x][Temp_y];
            Temp_y = Temp_y - (Temp_y & -Temp_y);
        }
        x = x - (x & -x);
    }
    return Result;
}

위와 같이 구간에 대한 합을 구하고 싶다면, 해당 구간에 존재하는 누적합을 구해주면 된다.

[ 소스코드 ]

#include<iostream>
#include<vector>
 
#define endl "\n"
#define MAX 1030
typedef long long ll;
using namespace std;
 
struct COMMAND
{
    int Cmd;
    int x;
    int y;
    int xx;
    int yy;
    int Value;
};
 
int N, M;
int MAP[MAX][MAX];
ll FenwickTree[MAX][MAX];
vector<COMMAND> Cmd;
 
void Input()
{
    cin >> N >> M;
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= N; j++)
        {
            cin >> MAP[i][j];
        }
    }
    for (int i = 0; i < M; i++)
    {
        int a; cin >> a;
        if (a == 1)
        {
            int x, y, xx, yy;
            cin >> x >> y >> xx >> yy;
            Cmd.push_back({ a, x, y, xx, yy, -1 });
        }
        else
        {
            int x, y, value;
            cin >> x >> y >> value;
            Cmd.push_back({ a, x, y, -1, -1, value });
        }
    }
}
 
void Update(int x, int y, ll Value)
{
    while (x < N + 1)
    {
        int Temp_y = y;
        while (Temp_y < N + 1)
        {
            FenwickTree[x][Temp_y] = FenwickTree[x][Temp_y] + Value;
            Temp_y = Temp_y + (Temp_y & -Temp_y);
        }
        x = x + (x & -x);
    }
}
 
void Make_FenwickTree()
{
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= N; j++ )
        {
            Update(i, j, MAP[i][j]);
        }
    }
}
 
ll Query(int x, int y)
{
    ll Result = 0;
    while (x > 0)
    {
        int Temp_y = y;
        while (Temp_y > 0)
        {
            Result = Result + FenwickTree[x][Temp_y];
            Temp_y = Temp_y - (Temp_y & -Temp_y);
        }
        x = x - (x & -x);
    }
    return Result;
}
 
void Solution()
{
    Make_FenwickTree();
    for (int i = 0; i < M; i++)
    {
        int Type = Cmd[i].Cmd;
        if (Type == 1)
        {
            int x = Cmd[i].x; int y = Cmd[i].y;
            int xx = Cmd[i].xx; int yy = Cmd[i].yy;
            cout << Query(xx, yy) - Query(xx, y - 1) - Query(x - 1, yy) + Query(x - 1, y - 1) << endl;
        }
        else
        {
            int x = Cmd[i].x;
            int y = Cmd[i].y;
            ll Value = Cmd[i].Value;
            ll Diff = Value - MAP[x][y];
            MAP[x][y] = Value;
            Update(x, y, Diff);
        }
    }
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}