이번에 풀어본 문제는
백준 2042번 구간 합 구하기 입니다.

📕 문제 링크

❗️코드

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

public class Main {
    static int N,M,K;
    static long [] map;
    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());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        map = new long[N+1];
        for(int i = 1; i <= N; ++i) map[i] = Long.parseLong(br.readLine());

        // 세그먼트 트리 생성
        tree = new long[N*4];
        setTree(1,N,1);

        int t = M+K;
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        while(t-- > 0)
        {
            st = new StringTokenizer(br.readLine());

            if(st.nextToken().equals("1")) // 변경
            {
                int idx = Integer.parseInt(st.nextToken());
                long val = Long.parseLong(st.nextToken());
                long diff = val-map[idx];
                update(1,N,1,idx,diff);
            }
            else // 합 찾기
            {
                int start = Integer.parseInt(st.nextToken());
                int end = Integer.parseInt(st.nextToken());
                bw.write(findSum(1,N,start,end,1)+"\n");
            }
        }
        bw.flush();
        bw.close();
    }
    static long setTree(int start,int end,int nodeNum)
    {
        if(start == end)
        {
            return tree[nodeNum] = map[start];
        }

        int mid = (start + end) / 2;
        return tree[nodeNum] = setTree(start,mid,nodeNum * 2) + setTree(mid+1,end,(nodeNum*2) + 1);
    }

    static void update(int start, int end,int nodeNum, int idx, long diff)
    {
        if(idx < start || idx > end) return;
        tree[nodeNum] += diff;
        if(start == end) map[idx] = tree[nodeNum];
        if(start != end)
        {
            int mid = (start + end) / 2;
            update(start,mid,nodeNum * 2,idx,diff);
            update(mid + 1,end,(nodeNum * 2) + 1,idx,diff);
        }
    }

    static long findSum(int start, int end, int left, int right, int nodeNum)
    {
        if((left > end) || (right < start)) return 0;
        else if((left <= start) && (right >= end)) return tree[nodeNum];
        else
        {
            int mid = (start + end) / 2;
            return findSum(start,mid,left,right,nodeNum * 2) + findSum(mid+1,end,left,right,(nodeNum * 2) + 1);
        }
    }
}

📝 풀이

M번 수정되는 N크기의 배열에서 K번 입력으로 주어지는 구간의 합을 출력하는 문제입니다.
명령은 M+K번 주어지고, 첫 번째 입력이 1일때는 수정, 2일때는 합을 구하여 출력해줍니다. 특정 구간의 합을 좀 더 효율적으로 구할 수 있는 알고리즘인 세그먼트 트리를 활용하여 풀어보았습니다.
세그먼트 트리를 활용하는 가장 기본적인 문제이며
https://www.acmicpc.net/blog/view/9
위 출처에 그림과 함께 이해하기 정말 쉽게 설명되어 있습니다.
참고하시면 도움이 될 것 같아요! ^^
이 문제에서는 주어진 입력값의 범위에 유의하여 자료형만 꼼꼼하게 체크한다면, 기본 적인 틀에서 벗어나지 않고 해결해낼 수 있습니다.

📜 후기

세그먼트 트리를 이전부터 풀어보려고 했었는데, 이제야 풀어봤네요 ㅋㅋㅋㅋ
구조 자체는 금방 이해한 것 같은데, 구현하는 과정을 좀 더 꼼꼼히 보았던 것 같습니다. 내일은 좀 더 심화문제를 풀어볼게요!