[ 백준 1275 ] 커피숍2 (C++)

백준의 커피숍(1275) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

구간에 대한 합을 구해야 하는 문제이다. 명령어 중간중간에는 값을 업데이트 해야 하는 부분도 있다.

'구간에 대한 연산'을 효율적으로 찾아낼 수 있는 세그먼트 트리를 통해서 해결할 수 있는 문제이다.

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

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

세그먼트 트리를 구현하는 내용만으로도 충분히 문제를 해결할 수 있기 때문에 별도의 설명 보다는 바로 소스코드로 대체하겠다.

[ 소스코드 ]

#include<iostream>
#include<vector>
#include<cmath>
#include<algorithm>
 
#define endl "\n"
#define MAX 100010
typedef long long ll;
using namespace std;
 
struct QUESTION
{
    int x;
    int y;
    int a;
    int b;
};
 
int N, Q;
ll Array[MAX];
vector<ll> SegmentTree;
vector<QUESTION> Cmd;
 
void Input()
{
    cin >> N >> Q;
    for (int i = 0; i < N; i++) cin >> Array[i];
    for (int i = 0; i < Q; i++)
    {
        int x, y, a, b;
        cin >> x >> y >> a >> b;
        x--; y--; a--; 
        Cmd.push_back({ x, y, a, b });
    }
}
 
ll Make_SegmentTree(int Node, int Start, int End)
{
    if (Start == End) return SegmentTree[Node] = (ll)(Array[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);
    
    return SegmentTree[Node] = Left_Result + Right_Result;
}
 
ll Section_Sum(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;
    ll Left_Result = Section_Sum(Node * 2, Start, Mid, Left, Right);
    ll Right_Result = Section_Sum(Node * 2 + 1, Mid + 1, End, Left, Right);
    return Left_Result + Right_Result;
}
 
void Update_Tree(int Node, int Start, int End, int Idx, ll Diff)
{
    if (Idx < Start || Idx > End) return;
    SegmentTree[Node] = SegmentTree[Node] + Diff;
    
    if (Start != End)
    {
        int Mid = (Start + End) / 2;
        Update_Tree(Node * 2, Start, Mid, Idx, Diff);
        Update_Tree(Node * 2 + 1, Mid + 1, End, Idx, Diff);
    }
}
 
void Solution()
{
    int Tree_Height = (int)ceil(log2(N));
    int Tree_Size = (1 << (Tree_Height + 1));
    SegmentTree.resize(Tree_Size);
    Make_SegmentTree(1, 0, N - 1);
 
    for (int i = 0; i < Cmd.size(); i++)
    {
        int x = Cmd[i].x;
        int y = Cmd[i].y;
        int a = Cmd[i].a;
        int b = Cmd[i].b;
        
        if (x > y) swap(x, y);
        cout << Section_Sum(1, 0, N - 1, x, y) << endl;
 
        ll Diff = b - Array[a];
        Array[a] = b;
        Update_Tree(1, 0, N - 1, a, 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;
}