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

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

1275번: 커피숍2

 

1. 주의할 점

- 세그먼트 트리에 대해 알고있어야 한다

 

2. 구현

- Height을 통해 세그먼트 트리를 나타낼 Tree[] 배열의 크기를 설정한다

- 초기의 수를 Arr[] 배열에 입력받은 후, Init() 함수를 통해 Tree를 초기화한다

- Query수만큼 Sum()과 Update() 함수를 호출하며, X가 Y보다 클 수도 있으므로 Big, Small 변수를 통해 큰값과 작은값을 저장한다

- 쿼리문을 실행할 경우, Sum() 수행 → Arr[] 배열 변경 → Update() 수행

#include <iostream>
#include <cmath>
using namespace std;
long long *tree;
long long arr[100000];

long long init(int node, int start, int end){
    if(start==end) return tree[node] = arr[start];
    int mid = start+(end-start)/2;
    return tree[node] = init(node*2, start, mid) + init(node*2+1, mid+1,end);
}

void update(int node, int start, int end, int idx, long long diff){
    if(start<=idx && idx<=end){
        tree[node]+=diff;
        if(start!=end){
            int mid = start+(end-start)/2;
            update(node*2, start, mid, idx, diff);
            update(node*2+1, mid+1, end, idx, diff);
        }
    }
}

long long 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[node];
    int mid = start+(end-start)/2;
    return sum(node*2, start, mid, left, right) + sum(node*2+1, mid+1, end, left, right);
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int num,height,query,x,y;
    long long a,b;
    cin>>num>>query;
    height = ceil(log2(num));
    tree = new long long [1<<(height+1)];
    for(int i=0;i<num;i++)
        cin>>arr[i];
    init(1,0,num-1);
    
    for(int i=0;i<query;i++){
        cin>>x>>y>>a>>b;
        int big = x>y ? x: y;
        int small = x>y ? y:x;
        cout << sum(1, 0, num-1, small-1, big-1)<<'\n';
        long long diff = b - arr[a-1];
        arr[a-1] = b;
        update(1,0,num-1,a-1, diff);
    }
    return 0;
}