[인덱스트리] 구간 합 구하기

백준 2042 구간 합 구하기

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

package 구간합구하기;

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

public class Main {

    static int N; //숫자개수
    static int M; //변경횟수
    static int K; //구간합을 구하는 횟수

    static long[] tree;
    static int k;
    static int treeSize; //크기는 2^k
    static int startIdx; //리프노드의 시작인덱스


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

        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개수 구하기
        k=0;
        while(N > Math.pow(2, k++)){}
        treeSize = (int)Math.pow(2,k);
        tree = new long[ treeSize ];
        startIdx = treeSize/2;

        //숫자 입력받음
        for(int i=0; i<N; i++){
            int a = Integer.parseInt(br.readLine());
            tree[startIdx+i] = a;
        }

        //트리 채우기
        fillTree(1);

        //변경 및 부분합 구하기
        for(int i=0; i<M+K; i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            //업데이트
            if(a==1){
                update(b,c); //b번째를 c로 바꾼다.
//                print();
            }

            //합 구하기

            if(a==2) System.out.println( sum(1,b,c, 1, (int)Math.pow(2,k-1)) );
        }
    }

    static void print(){
        for(long t: tree){
            System.out.printf("%d ", t);
        }
    }


    /**
     *
     * @param idx 현제위치
     * @param left 구하려고 하는 구간의 시작
     * @param right 구하려고 하는 구간의 끝
     * @param start 현재위치노드 자손 리프노드의 시작
     * @param end 현재위치노드 자손 리프노드의 끝
     * @return
     */
    static long sum(int idx, int left, int right, int start, int end){

        //현재구간이 구하려는 구간 바깥
        if(end < left || right < start){
            return 0;
        }

        //현재 구간이 구하려는 구간의 안쪽
        if(left <= start && end <=right){
            return tree[idx];
        }

        //현재구간과 구하려는 구간이 겹침
        return sum(idx*2, left, right, start, (start+end)/2) +
                sum(idx*2+1, left, right, (start+end)/2+1, end);
    }

    /**
     *
     * @param idx 번째 수를
     * @param num 으로 교체
     */
    static void update(int idx, int num){

        long delta = num - tree[startIdx + idx - 1];
        int updateIdx=startIdx + idx - 1;

//        System.out.printf("update(%d, %d) delta:%d, updateIndex:%d", idx, num, delta, updateIdx);


        while(0<updateIdx){
            tree[updateIdx] += delta;
            updateIdx /= 2;
        }
    }


    static long fillTree(int index){
        if(index < treeSize/2) return tree[index] = fillTree(index*2) + fillTree(index*2+1);
        else return tree[index];
    }
}

예전에 풀었을때와 아주 약간 다른 차이점

public static void updateHeap(int index, long diff) {
    arr[index] += diff;
    if(index != 1) updateHeap(index/2, diff);
}

이번에는 update를 반복문으로 했는데 예전엔 재귀로 했었음.

//트리 나머지 부분 채우기
for(int i=arr.length-1; 1<i; i--) {
    arr[i/2]+=arr[i];
}

이번에는 리프노드 채우는 걸 재귀로 했는데 예전엔 반복문으로 했었음.

예전에 푼 코드

public class Main {

    static long[] arr;

    public static void main(String[] args) throws IOException {
        // TODO Auto-generated method stub

        //N개의 정수를 배열로 받음
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt( st.nextToken() );
        int M = Integer.parseInt( st.nextToken() );
        int K = Integer.parseInt( st.nextToken() );


        int leafSize = (int) Math.pow(2.0, Math.floor((Math.log(N) / Math.log(2.0)) + 1));
        int treeSize = 2 * leafSize;
//        System.out.println("노드수: " + (treeSize-1));

        arr = new long[ treeSize ];


        //리프노드에 숫자 채우기
        int startIndex = treeSize/2;
        for(int i=startIndex; i<startIndex+N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        //트리 나머지 부분 채우기
        for(int i=arr.length-1; 1<i; i--) {
            arr[i/2]+=arr[i];
        }

        // 숫자뱐경 & 부분합구하기
        for(int i=0; i<K+M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            if(a==1) { //숫자변경
                int index = startIndex+b-1;
                long diff = c - arr[index];
                updateHeap(index, diff);
            }
            else if(a==2){ //부분합
                int left = startIndex+b-1;
                int right = startIndex+c-1;
//                System.out.println( countSum(left,right) );
                System.out.println( sum(b,c,1,1,startIndex-1) );
            }
        }
    }


    public static long sum(long L,long R ,int idx,int temp_L,int temp_R){
        if(temp_R<L||temp_L>R)return 0;
        if(L <=temp_L&&temp_R<=R)return arr[idx];
        int mid = (temp_R+temp_L)/2;
        return sum(L,R,idx*2,temp_L,mid)+sum(L,R,idx*2+1,mid+1,temp_R);
    }



    public static long countSum(int left, int right) {
        long sum=0;

        while(left<right) {

            //완료체크
            if(left==right) {
                sum += arr[left];
                break;
            }

            //left
            if(left%2==0) {
                left = left/2;
            }else {
                sum += arr[left];
                left++;
            }

            //완료체크
            if(left==right){
                sum += arr[left];
                break;
            }

            //right
            if(right%2==0) {
                sum += arr[right];
                right=(right-1)/2;
            }else {
                right=right/2;
            }

        }//while

        return sum;
    }


    public static void updateHeap(int index, long diff) {
        arr[index] += diff;
        if(index != 1) updateHeap(index/2, diff);
    }


    public static void print(int[] arr) {
        for(int i=1; i<arr.length; i++) {
            System.out.printf("%d ", arr[i]);
        }
    }


}

countSum은 삼성SDS 강사분이 가르쳐준 방법.

sum처럼 하는게 더 깔끔한 것 같다.