[백준✨] 2042번 <구간합 구하기> / JAVA 문제풀이 / 인덱스 트리

해답)

package 구간합구하기;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    static long []numbers;
    static int N, M, K;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] line = br.readLine().split(" ");
        N = Integer.parseInt(line[0]);
        M = Integer.parseInt(line[1]);
        K = Integer.parseInt(line[2]);
        numbers = new long[N+1];
        numbers[0] = 0;
        for (int i=0; i < N; i++) {
            numbers[i+1] = Long.parseLong(br.readLine());
        }
        IndexedTree it = new IndexedTree(numbers);
        it.makeTree();

        for (int i=0; i<M+K; i++) {
            line = br.readLine().split(" ");
            if (Integer.parseInt(line[0]) == 1) { // 특정 수 바꾸기
                int targetIndex = Integer.parseInt(line[1]);
                int targetValue = Integer.parseInt(line[2]);
                it.update(targetIndex,targetValue);
            }
            else{ // 구간합 구하기
                int startIndex = Integer.parseInt(line[1]);
                int endIndex = Integer.parseInt(line[2]);
                System.out.println(it.getPartialSum(startIndex, endIndex));
            }
        }
    }
}

class IndexedTree { // nums 의 맨 앞 요소는 0과 같은 버리는 값 넣어줘야한다.
    long[] tree;
    long[] nums;
    int leafSize, depth;

    IndexedTree(long[] nums){
        this.nums = nums;
        this.depth = 0;
        while(Math.pow(2,depth) < nums.length-1){
            this.depth++;
        }
        this.leafSize = (int)(Math.pow(2, this.depth));
        tree = new long[(int) Math.pow(2, this.depth+1)];
    }

    public void makeTree() {
        subMakeTree(1, 1, this.leafSize);
    }

    //내부 노드의 값 체워주기
    public long subMakeTree(int node, int left, int right) {
        if(left == right) {
            if (left < nums.length) {
                return tree[node] = nums[left];
            }
            else{
                return tree[node] = 0;
            }
        }
        int mid = (left + right) / 2;
        tree[node] = subMakeTree(node*2, left, mid);
        tree[node] += subMakeTree(node*2+1, mid+1, right);
        return tree[node];
    }

    public long getPartialSum(int startIndex, int endIndex) {
        return query(1, 1, this.leafSize, startIndex, endIndex);
    }

    public long query(int node, int left, int right, int qLeft, int qRight) {
        if (qRight < left || qLeft > right) { // 관련 없는경우
            return 0;
        }
        if (qLeft <= left && right <= qRight) { // 쿼리 안에 속하는 경우
            return tree[node];
        }
        int mid = (left + right) / 2;
        return query(node*2, left, mid, qLeft, qRight) +
                query(node*2+1, mid+1, right, qLeft, qRight);
    }

    public void update(int targetIndex, long targetValue) {
        long diff = targetValue - nums[targetIndex];
        subUpdate(1, 1, leafSize, targetIndex, diff);
        nums[targetIndex] = targetValue;
    }

    public void subUpdate(int node, int left, int right, int index, long diff){
        if (index < left || right < index) { // 관련 없는 경우
            return ;
        }
        else{
            tree[node] += diff;
            if (left != right) {
                int mid = (left + right) / 2;
                subUpdate(node*2, left, mid, index, diff);
                subUpdate(node*2+1, mid+1, right, index, diff);
            }
        }
    }

    @Override
    public String toString() {
        return "IndexedTree{" +
                "tree=" + Arrays.toString(tree) +
                ", nums=" + Arrays.toString(nums) +
                ", leafSize=" + leafSize +
                ", depth=" + depth +
                '}';
    }
}

---

풀이)

 

인덱스 트리의 원리를 이용하면 쉽게 구할 수 있습니다!

인덱스 트리의 장점

1. 구간 합 구하기 시간복잡도 => O(logN)

2. 특정 인덱스 바꾸기 시간복잡도 => O(logN)
을 이용한 문제입니다.

 

인덱스 트리에 대한 정보와 코드의 class IndexTree 에 대한 해설은 

여기서 확인하실 수 있습니다! 

 

 

* 위 문제의 저작권은 백준(https://www.acmicpc.net/) 에 있습니다.