최근에 회사 일이 너무 바빠서 ㅜ 어제는 공부를 못했다 ㅠ...

문제링크

백준 #2042. 구간 합 구하기

풀이방법

오오 전에 푼 백준 > #11659. 구간 합 구하기4 이 문제랑 비슷하다! 다른 점은 "중간에 수의 변경이 빈번히 일어난다" 이 조건이다. 흐음.. 이런 조건이 있는 문제에 전 문제와 같이 구간합 배열을 사용한다면 매번 배열을 다시 구성해 수의 변경에 대해 O(MN)의 시간복잡도를 갖는다. 그럼 M과 N의 범위를 보아 바아로 시간초과가 나겠쥬,,? 변경 시 구간 합 갱신을 어떻게 효율적으로 처리할 수 있는지가 이 문제의 핵심이다!

O(N)보다 빠른 시간복잡도를 생각하면 O(logn).. O(logn)하면 Tree! 그 중에 각 노드에 구간 혹은 그 구간의 정보를 저장하고 있는 세그먼트 트리를 사용하면 이 문제를 해결할 수 있다. 세그먼트 트리 내 구간정보를 구간에 속한 원소들의 합으로 하는거야! 코드 내에 쓰인 연산들을 설명하겠습니다~

update 연산
바꾸고자 하는 수의 위치와 값을 입력받는다. 그럼 그 위치를 배열 내에서 쓰는 index로 전환하고 해당 index의 값을 바꾼다. 그리고 트리를 위로 타고 올라가면서 루트까지 값을 바꾸는 연산을 진행한다.

sum 연산
재귀함수이다. 총 세가지 케이스를 가진다.
#1. 현재 노드의 범위가 목표 범위에 완전히 속한다.
-> 해당 노드의 값을 리턴한다. 당연히 더 들어갈 이유가 없죠?
#2. 현재 노드의 범위가 목표 범위의 일부에 속한다.
-> 속하지 않는 부분도 있기때문에 반으로 나눠 sum 함수를 호출한다. 그리고 그 합을 리턴~
#3. 아예 겹치지 않는다.
-> 0 리턴

+) construct 연산
완전 필수는 아니지만 초기에 트리를 구성할 때 좀 더 효율적으로 할 수 있는 방법이다. 리프노드를 다 채워놓고 그 위 레벨부터 채워가 O(N)만에 트리를 구성하는 방법! 이렇게 하지 않으면 하나하나 넣고 update 연산을 진행해야하는데 이 경우엔 O(nlogn)의 시간복잡도를 갖겠죠? 굳이굳이~_~

코드

import java.util.Scanner;

public class SumOfIntervals2042 {
    static int startIndex;
    static long[] arr;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int m = sc.nextInt();
        int k = sc.nextInt();

        getStartIndex(n, 1);
        arr = new long[startIndex * 2 - 1 + 1];
        int tempIndex = startIndex;
        while (tempIndex <= (startIndex * 2 - 1)) { // startIndex부터 n개의 값을 트리에 삽입
            if (--n >= 0) arr[tempIndex++] = sc.nextInt();
            else arr[tempIndex++] = 0;
        }
        constructTree();

        StringBuilder result = new StringBuilder();
        for (int i = 0; i < (m + k); i++) {
            int op = sc.nextInt();

            if (op == 1) update(startIndex - 1 + sc.nextInt(), sc.nextInt());
            else {
                result.append(sum(sc.nextInt(), sc.nextInt(), 1, 1, startIndex));
                result.append("\n");
            }
        }

        System.out.print(result);
    }

    // 세그먼트 트리의 특성상, 크기를 2^k 꼴로 맞추는게 필요함
    static void getStartIndex(int n, int index) {
        if (index >= n) startIndex = index;
        else getStartIndex(n, index * 2);
    }

    // 하나하나 업데이트 연산(O(nlogn))을 할 수도 있지만, 초기에는 리프노드를 참고해 한번에 트리를 구성(O(n))
    static void constructTree() {
        for (int i = startIndex - 1; i > 0; --i) {
            arr[i] = arr[i * 2] + arr[i * 2 + 1];
        }
    }

    static void update(int index, int value) {
        arr[index] = value;

        // 바뀐 리프노트에서 루트로 올라가면서 그 값들을 갱신해줌
        while (index != 1) {
            index /= 2;
            arr[index] = arr[index * 2] + arr[index * 2 + 1];
        }
    }

    static long sum(int l, int r, int nodeIndex, int nodeL, int nodeR) {
        if ((l > nodeR) || (r < nodeL)) return 0;
        else if ((l <= nodeL) && (r >= nodeR)) return arr[nodeIndex];
        int mid = (nodeL + nodeR) / 2;
        return sum(l, r, nodeIndex * 2, nodeL, mid) + sum(l, r, nodeIndex * 2 + 1, mid + 1, nodeR);
    }
}

🔥

불금입니당