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

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

[ 문제 바로가기 ]

[ 문제풀이 ]

구간의 합을 구해야 하는 문제이다. 본인은 총 3가지 방법을 이용해서 문제를 해결해 보았다.

첫 번째는 간단하게 누적합을 미리 구해놓고 이 누적합을 통해서 구하는 방법이다.

이 문제는 배열의 값을 변경하는 업데이트 과정이 존재하지 않기 때문에, 단순히 누적합을 구해놓고 풀어보았다.

구체적인 과정을 알아보자. 배열이 { 1 , 2 , 3 , 4 , 5 } 가 존재한다면, 0번째 Index부터 k번째 Index까지의 합을 저장하는 누적합에 대한 배열을 하나 더 선언해 주었다.(int Sum[])

Sum[a] = b 의 의미는 "0번 Index부터 a번 Index까지의 합은 b입니다." 를 의미한다.

즉, 위의 배열({ 1, 2, 3, 4, 5}) 를 예로들어서 값을 적어보면 Sum[0] = 1 , Sum[1] = 3(1 + 2) , Sum[2] = 6(1 + 2 + 3)... 과 같은 식으로 저장이 된다.

a번에서 b번 Index까지의 값을 구하라고 한다면 Sum[b] - Sum[a - 1] 을 통해서 그 값을 구할 수 있다.

가장 간단하고 구현이 쉬운 방법이다.

두 번째는 세그먼트 트리를 이용해서 구해보았다. 값의 업데이트가 필요하지 않기 때문에 첫 번째 방법으로 구현해도 무관하지만, 세그먼트 트리로도 구현해 보았다. 세그먼트 트리에 대해서 잘 모른다면 아래의 글을 읽고 오도록 하자.

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

세그먼트 트리에 대한 설명글만으로도 충분히 문제를 해결할 수 있기 때문에 별도의 설명은 하지 않겠다.

세 번째는 펜윅 트리를 이용해서 구해보았다. 세그먼트 트리와 마찬가지로, 값의 업데이트가 일어나지 않기 때문에 꼭 사용할 필요까지는 없지만, 펜윅트리 또한 구간에 대한 연산에서 굉장히 효율적인 자료구조 이기 때문에 이를 이용해서 구현해 보았다.

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

펜윅트리 또한 별도의 설명은 하지 않겠다.

[ 방법1. 단순 누적합을 통한 구현 소스코드 ]

#include<iostream>
#include<vector>
#include<cmath>
 
#define endl "\n"
#define MAX 100010
using namespace std;
 
int N, M;
int Arr[MAX];
int Sum[MAX];
vector<pair<int, int>> Cmd;
 
void Input()
{
    cin >> N >> M;
    for (int i = 1; i <= N; i++)
    {
        cin >> Arr[i];
        Sum[i] = Sum[i - 1] + Arr[i];
    }
    for (int i = 0; i < M; i++)
    {
        int a, b; cin >> a >> b;
        Cmd.push_back(make_pair(a, b));
    }
}
 
void Solution()
{
    for (int i = 0; i < M; i++)
    {
        int Start = Cmd[i].first;
        int End = Cmd[i].second;
 
        cout << Sum[End] - Sum[Start - 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;
}

[ 방법2. 세그먼트 트리를 이용한 소스코드 ]

#include<iostream>
#include<vector>
#include<cmath>
 
#define endl "\n"
#define MAX 100010
using namespace std;
 
int N, M;
int Arr[MAX];
vector<int> SegmentTree;
vector<pair<int, int>> Cmd;
 
void Input()
{
    cin >> N >> M;
    for (int i = 1; i <= N; i++) cin >> Arr[i];
    for (int i = 0; i < M; i++)
    {
        int a, b; cin >> a >> b;
        Cmd.push_back(make_pair(a, b));
    }
}
 
int Make_SegmentTree(int Node, int Start, int End)
{
    if (Start == End) return SegmentTree[Node] = Arr[Start];
    
    int Mid = (Start + End) / 2;
    int Left_Result = Make_SegmentTree(Node * 2, Start, Mid);
    int Right_Result = Make_SegmentTree(Node * 2 + 1, Mid + 1, End);
    return SegmentTree[Node] = Left_Result + Right_Result;
}
 
int Query(int Node, int Start, int End, int Left, int Right)
{
    if (Right < Start || Left > End) return 0;
    if (Left <= Start && End <= Right) return SegmentTree[Node];
 
    int Mid = (Start + End) / 2;
    int Left_Result = Query(Node * 2, Start, Mid, Left, Right);
    int Right_Result = Query(Node * 2 + 1, Mid + 1, End, Left, Right);
    return Left_Result + Right_Result;
}
 
void Solution()
{
    int Tree_Height = (int)ceil(log2(N));
    int Tree_Size = 1 << (Tree_Height + 1);
    SegmentTree.resize(Tree_Size);
    Make_SegmentTree(1, 1, N);
 
    for (int i = 0; i < M; i++)
    {
        int Idx = Cmd[i].first;
        int Idx2 = Cmd[i].second;
 
        cout << Query(1, 1, N, Idx, Idx2) << 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;
}

[ 방법3. 펜윅트리를 이용한 소스코드 ]

#include<iostream>
#include<vector>
#include<cmath>
 
#define endl "\n"
#define MAX 100010
using namespace std;
 
int N, M;
int Arr[MAX];
vector<int> FenwickTree;
vector<pair<int, int>> Cmd;
 
void Input()
{
    cin >> N >> M;
    for (int i = 1; i <= N; i++) cin >> Arr[i];
    for (int i = 0; i < M; i++)
    {
        int a, b; cin >> a >> b;
        Cmd.push_back(make_pair(a, b));
    }
}
 
void Update(int Idx, int Value)
{
    while (Idx < FenwickTree.size())
    {
        FenwickTree[Idx] = FenwickTree[Idx] + Value;
        Idx = Idx + (Idx & -Idx);
    }
}
 
int Sum(int Idx)
{
    int Result = 0;
    while (Idx > 0)
    {
        Result = Result + FenwickTree[Idx];
        Idx = Idx - (Idx & -Idx);
    }
    return Result;
}
 
void Solution()
{
    FenwickTree.resize(N + 1);
    for (int i = 1; i <= N; i++) Update(i, Arr[i]);
    for (int i = 0; i < M; i++)
    {
        int Start = Cmd[i].first;
        int End = Cmd[i].second;
        
        cout << Sum(End) - Sum(Start - 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;
}