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

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

[ 문제 바로가기 ]

[ 문제풀이 ]

먼저 문제를 보면 구간에 대한 합을 구하는 문제이다. 구간에 대한 연산은 "세그먼트 트리" 혹은 "펜윅트리"를 이용해서 빠르고 효율적으로 해결할 수 있다.

본인은 세그먼트 트리로 이 문제에 접근해보았는데 아직 세그먼트 트리에 대해서 잘 모른다면 아래의 글을 읽고 오도록 하자.

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

그런데 ! 이 문제는 단순 세그먼트 트리를 이용해서 구현한다면 시간초과가 발생하게 된다. 왜냐하면 값을 업데이트 하는 것 또한 구간의 개념으로 주어지기 때문에, 제 시간 내에 연산을 다 할 수가 없다. 그래서 'Lazy Propagation' 방식을 이용해서 구현해주어야 한다. 아직 Lazy Propagation에 대해서 잘 모른다면 아래의 글을 읽고 오도록 하자.

[ Lazy Propagation 알아보기 (Click) ]

위에 링크를 걸어놓은 세그먼트 트리에 대한 설명과, Lazy Propagation 설명에 대한 글 만으로도 이 문제의 풀이를 충분히 대체할 수 있기 때문에 별다른 추가적인 설명은 진행하지 않겠다.

[ 소스코드 ]

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