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

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

[ 문제 바로가기 ]

[ 문제풀이 ]
이 문제는 세그먼트 트리 혹은 펜윅트리를 이용해서 구할 수 있는 문제이다.

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

[ 세그먼트 트리 알아보기(Click) ]

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

위의 자료구조들을 설명하는 글 만으로도 이 문제에 대한 풀이를 대체할 수 있기 때문에 별도의 설명은 하지 않겠다.

단지, 주어지는 수가 int형의 범위를 벗어날 수 있기 때문에 long long 자료형을 사용해 주어야 한다.

소스코드는 세그먼트트리를 이용한 코드와, 펜윅트리를 이용한 코드 2개를 첨부해 놓겠다.

[ 세그먼트 트리 소스코드 ]

#include<iostream>
#include<vector>
#include<cmath>
 
typedef long long ll;
using namespace std;
 
int N, M, K;
vector<ll> Arr;
vector<ll> Tree_Array;
vector<pair<int, pair<int, ll>>> Cmd;
 
void Input()
{
    cin >> N >> M >> K;
    for (int i = 0; i < N; i++)
    {
        int a; cin >> a;
        Arr.push_back(a);
    }
    for (int i = 0; i < M + K; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        Cmd.push_back(make_pair(a, make_pair(b, c)));
    }
}
 
ll Make_SegmentTree(int Node, int Start, int End)
{
    if (Start == End) return Tree_Array[Node] = Arr[Start];
    
    int Mid = (Start + End) / 2;
    ll Left_Result = Make_SegmentTree(Node * 2, Start, Mid);
    ll Right_Result = Make_SegmentTree(Node * 2 + 1, Mid + 1, End);
    Tree_Array[Node] = Left_Result + Right_Result;
    return Tree_Array[Node];
}
 
ll Sum(int Node, int Start, int End, int Left, int Right)
{
    if (Left > End || Right < Start) return 0;
    if (Left <= Start && End <= Right) return Tree_Array[Node];
 
    int Mid = (Start + End) / 2;
    ll Left_Result = Sum(Node * 2, Start, Mid, Left, Right);
    ll Right_Result = Sum(Node * 2 + 1, Mid + 1, End, Left, Right);
    return Left_Result + Right_Result;
}
 
void Update_SegmentTree(int Node, int Start, int End, int Index, ll Diff)
{
    if (Index < Start || Index > End) return;
    Tree_Array[Node] = Tree_Array[Node] + Diff;
 
    if (Start != End)
    {
        int Mid = (Start + End) / 2;
        Update_SegmentTree(Node * 2, Start, Mid, Index, Diff);
        Update_SegmentTree(Node * 2 + 1, Mid + 1, End, Index, Diff);
    }
}
 
void Solution()
{
    int Tree_Height = (int)ceil(log2(N));
    int Tree_Size = (1 << (Tree_Height + 1));
    Tree_Array.resize(Tree_Size);
    Make_SegmentTree(1, 0, N - 1);
 
    for (int i = 0; i < Cmd.size(); i++)
    {
        int Command = Cmd[i].first;
        if (Command == 1)
        {
            int Index = Cmd[i].second.first - 1;
            ll Value = Cmd[i].second.second;
            ll Diff = Value - Arr[Index];
            Arr[Index] = Value;
            Update_SegmentTree(1, 0, N - 1, Index, Diff);
        }
        else
        {
            int Index = Cmd[i].second.first - 1;
            int Index2 = Cmd[i].second.second - 1;
            ll Result = Sum(1, 0, N - 1, Index, Index2);
            cout << Result << endl;
        }
    }
}
 
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;
}

[ 펜윅트리 소스코드 ]

#include<iostream>
#include<vector>
#include<cmath>
 
typedef long long ll;
using namespace std;
 
int N, M, K;
vector<ll> Arr;
vector<ll> Fenwick_Tree;
vector<pair<int, pair<int, ll>>> Cmd;
 
void Input()
{
    cin >> N >> M >> K;
    Arr.resize(N + 1);
    Fenwick_Tree.resize(N + 1);
    
    for (int i = 1; i <= N; i++)
    {
        int a; cin >> a;
        Arr[i] = a;
    }
    for (int i = 0; i < M + K; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        Cmd.push_back(make_pair(a, make_pair(b, c)));
    }
}
 
void Update(int Idx, ll Value)
{
    while (Idx < Fenwick_Tree.size())
    {
        Fenwick_Tree[Idx] = Fenwick_Tree[Idx] + Value;
        Idx = Idx + (Idx & -Idx);
    }
}
 
void Make_PenwickTree()
{
    for (int i = 1; i <= N; i++)
    {
        Update(i, Arr[i]);
    }
}
 
ll Sum(int Idx)
{
    ll Result = 0;
    while (Idx > 0)
    {
        Result = Result + Fenwick_Tree[Idx];
        Idx = Idx - (Idx & -Idx);
    }
    return Result;
}
 
void Solution()
{
    Make_PenwickTree();
 
    for (int i = 0; i < Cmd.size(); i++)
    {
        int Num = Cmd[i].first;
        if (Num == 1)
        {
            int Index = Cmd[i].second.first;
            ll Value = Cmd[i].second.second;
            ll Diff = Value - Arr[Index];
            Arr[Index] = Value;
            Update(Index, Diff);
        }
        else
        {
            int Index = Cmd[i].second.first;
            int Index2 = Cmd[i].second.second;
            cout << Sum(Index2) - Sum(Index - 1) << endl;
        }
    }
}
 
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;
}