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

 

링크 : https://www.acmicpc.net/problem/1275

1275번: 커피숍2

 

문제 설명 : 

모두 알다시피 동호는 커피숍의 마담이다. (마담이 무엇인지는 본인에게 물어보도록 하자.)

어느 날 커피숍의 손님 A씨가 동호에게 게임을 하자고 했다.

그 게임은 다음과 같은 규칙을 갖는다.

N개의 정수가 있으면, 동호는 다음과 같이 말한다. “3~7번째 수의 합은 무엇이죠?” 그러면 상대방은 “그 답은 000입니다. 그리고 8번째 수를 2로 고치도록 하죠” 그러면 동호는 “네 알겠습니다.”라고 한 뒤에 다시 상대방이 동호가 했던 것처럼 “8~9번째 수의 합은 무엇이죠?”라고 묻게된다. 이 것을 번갈아 가면서 반복하는 게임이다.

당신은 이 게임의 심판 역을 맡았다. 요컨대, 질문에 대한 답들을 미리 알아야 한다는 것이다.

당신의 머리가 출중하다면 10만개 가량 되는 정수와 10만턴 정도 되는 게임을 기억할 수 있을 것이다. 몇판 이 게임을 즐기던 동호는 많은 사람들이 이 게임을 하기를 바라게 되었고, 당신에게 심판 프로그램을 구현해달라고 요청했다.

한 턴마다 구한 합을 한 줄마다 한 개씩 출력한다.

 

x~y는 당연히 x번째 부터 y번째가 맞다. 하지만, 이 문제에서는 x > y인 경우 y번째 부터 x번째이다.

 

입력 : 

첫째 줄에 수의 개수 N과 턴의 개수 Q가 주어진다.(1 ≤ N, Q ≤ 100,000) 둘째 줄에는 처음 배열에 들어가 있는 정수 N개가 주어진다. 세 번째 줄에서 Q+2번째 줄까지는 x y a b의 형식으로 x~y까지의 합을 구하여라, a번째 수를 b로 바꾸어라 라는 뜻의 데이터가 주어진다.

입력되는 모든 수는 -231보다 크거나 같고, 231-1보다 작거나 같은 정수이다.

출력 : 

한 턴마다 구한 합을 한 줄마다 한 개씩 출력한다.

 

예제 입력 : 

5 2
1 2 3 4 5
2 3 3 1
3 5 4 1

예제 출력 : 

5
10

 

 

접근법 : 

1) 어떻게 풀 것인가?

세그먼트 트리 (재귀함수) 스타일의 풀이

 

2) 시간복잡도

 

 

3) 공간복잡도

 

 

4) 풀면서 놓쳤던점

 

 

5) 이 문제를 통해 얻어갈 것

 

 

 

세그먼트 트리 스타일 - C++ 코드 : 

#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;
}

 

인덱스드트리 스타일 - C++코드 : 

#include <cstdio>
#define MAX_N 100000
#define SZ_TR 1000001
using namespace std;

typedef long long ll;

ll tree[SZ_TR];
ll tmp[MAX_N + 1];
ll OFFSET;
void init(ll n) {
    for (OFFSET = 1; OFFSET < n; OFFSET *= 2);
    for (ll i = 1; i <= n; i++) tree[OFFSET + i] = tmp[i];
    for (ll i = n + 1; i < OFFSET; i++)tree[OFFSET + i] = 0; 
    for (ll i = OFFSET - 1; i > 0; --i) tree[i] = tree[i * 2] + tree[i * 2 + 1];
    tree[OFFSET] = 0;
}
ll query(ll from, ll to) {
    ll res = 0;
    from += OFFSET, to += OFFSET;
    while (from <= to) {
        if (from % 2 == 1) {
            res += tree[from++];
        }
        if (to % 2 == 0) {
            res += tree[to--];
        }
        from /= 2, to /= 2;
    }
    return res;
}
void update(ll idx, ll val) {
    idx += OFFSET;
    tree[idx] = val;
    idx /= 2;
    while (idx >= 1) {
        tree[idx] = tree[idx * 2] + tree[idx * 2 + 1];
        idx /= 2;
    }
}
int main() {

    int N, Q;
    int x, y, a, b;

    scanf("%d %d", &N, &Q);
    for (int i = 1; i <= N; i++) scanf("%lld", tmp + i);
    init(N);
    for (int i = 0; i < Q; i++) {
        ll t1, t2, t3, t4;
        scanf("%lld %lld %lld %lld", &t1, &t2, &t3, &t4);
        
        if (t1 > t2) {
            ll tmp = t1;
            t1 = t2;
            t2 = tmp;
        }
        printf("%lld\n", query(t1, t2));
        update(t3, t4);
    }
    return 0;
}