[백준 코딩테스트] 백준 1275번 커피숍2

문제 풀이

처음에는 그냥 배열로 풀려고 하다가 주어진 범위를 보고 세그먼트 트리를 이용하여 풀었다. 풀다보니 백준 2042번 구간 합 구하기 문제의 형식과 비슷함을 알게 되었다.

처음에는 트리를 초기화 해준 후, 주어진 x ~ y 사이의 합을 먼저 구해준다. 초기화와 합을 구해주는 것은 2042번과 다르지 않았다.

그 후 a번째 수를 b로 바꿔줘야 한다.
이 점이 2042번과 달랐다.
이 코드에서는 굳이 diff를 구해서 풀지 않고, 해당 idx에 도달할 때까지 mid값을 갱신해주며 왼쪽 오른쪽 노드를 방문하여 idx에 도달하면 트리와 입력받은 배열의 a번째 값을 b로 바꿔준다.

이때 트리의 합도 갱신해줌을 잊지말자 !!

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static long[] arr;
    static long[] tree;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

        int n = Integer.parseInt(st.nextToken());
        int q = Integer.parseInt(st.nextToken());

        arr = new long[n+1];
        tree = new long[4*n];

        st = new StringTokenizer(br.readLine());

        for(int i=1; i<=n; i++){
            arr[i] = Long.parseLong(st.nextToken());
        }

        init(1, n, 1);

        for(int i=0; i<q; i++){
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            sb.append(sum(1, n, 1, Math.min(x, y), Math.max(x, y)) + "\n");

            update(1, n, 1, a, b);
        }

        System.out.println(sb);
    }

    // 트리 초기화
    static long init(int start, int end, int node){
        if(start==end){
            return tree[node] = arr[start];
        }

        int mid = (start+end)/2;

        return tree[node]=init(start, mid, node*2)+init(mid+1, end, node*2 +1);
    }

    // 합 
    static long sum(int start, int end, int node, int left, int right){
        if(left>end ||  right<start) return 0;
        if(left<=start && end<= right) return tree[node];

        int mid=(start+end)/2;
        return sum(start, mid, node * 2, left, right) + sum(mid + 1, end, node * 2 + 1, left, right);
    }

    // 업데이트
    static void update(int start, int end, int node, int idx, long val){
        if (idx < start || idx > end) return;
    
        if (start == end) { // idx 노드 값 변경
            tree[node] = val;
            arr[idx] = val;
            return;
        }
    
        int mid = (start + end) / 2;
        update(start, mid, node * 2, idx, val);
        update(mid + 1, end, node * 2 + 1, idx, val);
    
        tree[node] = tree[node * 2] + tree[node * 2 + 1];
    }
    
}