[BOJ] 구간 합 구하기

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

2042번: 구간 합 구하기

 

Segment Tree 를 활용하여 풀 수 있는 문제

 

2021.08.22 - [Algorithm - 이론] - [트리] 세그먼트 트리 - 부분 합 효율적으로 구하기

[트리] 세그먼트 트리 - 부분 합 효율적으로 구하기

 

소스코드

import java.io.*;
import java.util.*;

public class BOJ2042 {

    public static long A[];
    public static long tree[];

    // Segment Tree 초기화
    public static long init(int start, int end, int node){

        if(start == end) return tree[node] = A[start];

        int mid = (start + end) / 2;

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

    // Segment Tree 활용해서 합 구하기
    public static long getSum(int start, int end, int left, long right, int node){

        // 구하려는 범위가 현재 노드의 범위가 전혀 겹치지 않을 경우
        if(right < start || end < left) return 0;

        // 현재 노드 범위가 구하려는 범위에 포함될 경우
        if(start >= left && end <= right) return tree[node];

        int mid = (start + end) / 2;

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

    // update
    public static void update(int start, int end, int idx, long diff, int node){
        
        // update 해야 하는 값이 범위에 포함되지 않는 경우
        if(idx < start || end < idx) return;

        int mid = (start + end) / 2;
        tree[node] -= diff;
        if(start == end) return;
        update(start, mid, idx, diff, node*2);
        update(mid+1, end, idx, diff, node*2+1);

    }


    public static void main(String[] args) throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;

        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        A = new long[n];

        for(int i=0; i<n; i++){
            st = new StringTokenizer(br.readLine());
            A[i] = Long.parseLong(st.nextToken());
        }

        // Segment Tree 초기화
        tree = new long[A.length * 4];
        init(0, A.length-1, 1);

        //printArray();

        for(int i=0; i<m+k; i++){
            st = new StringTokenizer(br.readLine());
            int control = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            long c = Long.parseLong(st.nextToken());

            if(control == 1){
                // update 함수 사용
                update(0, A.length-1, b-1, A[b-1]-c, 1);
                A[b-1] = c;
                // update 함수 미사용 시 - 전체 트리를 다시 update 하므로 시간초과
                // A[b-1] = c;
                // init(0,A.length-1, 1);
            }else{
                // sum
                System.out.println(getSum(0, A.length-1, b-1, c-1, 1));
            }
        }

    }

    public static void printArray(){
        System.out.print("A : ");
        for(long a : A){
            System.out.print(a + " ");
        }
        System.out.println();
        System.out.print("Tree : ");

        for(long a : tree){
            System.out.print(a + " ");
        }
        System.out.println();
    }
}