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

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

문제 자체는 단순하게 조건에 맞는 세그먼트 트리를 구현하는 문제이다... 하지만 나는 아직 세그먼트 트리를 잘 이해하지 못한것 같다 😓 풀면서 헷갈렸던 점 위주로 정리했다.

• 초기 배열 값 입력받을때 i=1 부터 받기

처음에 배열값들 입력받을때도 1부터 입력받아야 헷갈리지 않는다.
처음 트리 만드는 함수에서 start, end는 array의 범위이고 세그먼트 트리에서 값 찾는 함수에서 start, end는 Tree의 범위이기 때문에.... 차라리 array 입력받을때부터 1로 받아서 둘다 1~N 범위로 생각하는게 깔끔하다

• update 함수 사용시 주의사항

여기서 계속 틀렸는데... 먼저 나는 변수 하나 지정해서 long long tmp = -array[a] + b 처럼 원래 값과 바꾸는 값의 차이를 저장한다음 index가 속한 seg Tree에 tmp값만큼 더해서 업데이트했다. 그런데 마지막에 array[a]=b도 해야한다는걸 생각 못했다.
처음에는 왜..?해야하는지 인지를 못했다 array 배열은 처음 seg Tree를 만들때만 사용한다고 생각했기 때문에...ㅋ 하지만 간과한 사실은 array[a]를 바꾸지 않는다면 array[a]값을 두번이상 바꿀때 에러가 난다.
도저히 안풀려서 update하는 함수의 인자를 차이가 아니라 바꾸는 값 자체로 했는데 에러가 안나서 알아챘다..ㅋ ㅠ;;

그리고 update함수 작성할때 생각하지 못했던것 : index는 어차피 mid기준 이전이거나 이후 둘중 하나에 속하게 된다. 그래서 index가 속하는 범위만 업데이트해도 된다.
index범위에 대해 예외처리해도 되긴 하지만.. 애초에 불필요하게 함수 호출하는거보다 이게 더 효율적인거같다.

long long update(int node, int s, int e, int index, long long chv) {

    Tree[node] += chv;
    if (s == e) return 0;

    int mid = (s + e) / 2;

    if (ch <= mid)
        return update(2 * node, s, mid, index, chv);

    else
        return update(2 * node + 1, mid + 1, e, index, chv);
}

전체코드

#include <iostream>
using namespace std;

int N,Q;
int x,y,a,b;
long long Tree[100005*4];
long long arr[100005];


long long makeTree(int start, int end, int node){

    if(start==end) return Tree[node] = arr[start];
    int mid = (start+end)/2;
    return Tree[node] = makeTree(start, mid, node*2) + makeTree(mid+1, end, node*2+1);

}


long long findSum(int start, int end, int left, int right, int node){

    if(left>end || right<start) return 0;

    if(left<=start && right>=end) return Tree[node];

    int mid = (start+end)/2;

    return findSum(start, mid, left, right, node*2) + findSum(mid+1, end, left, right, node*2+1);


}

void updateTree(int start, int end, int node, int index, long long dif){

    if(index<start || index>end) return ;

    Tree[node] += dif;
    if(start==end) return ;

    int mid = (start+end)/2;
    updateTree(start, mid, node*2, index, dif);
    updateTree(mid+1, end, node*2+1, index, dif);
    return ;
}


int main() {

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>N>>Q;

    for(int i=1; i<=N; i++) cin>>arr[i];

    makeTree(1, N, 1);

    while(Q--){
        cin>>x>>y>>a>>b;
        if(x>y) swap(y,x);
        cout<<findSum(1, N, x, y, 1)<<'\n';

        long long tmp = -arr[a]+b;
        updateTree(1, N, 1, a, tmp);
        arr[a]=b;
    }


}