[백준] 11505번 구간 곱 구하기 _ JAVA ( 주석 설명 )

풀이

'부모노드 = 왼쪽 자식노드 * 오른쪽 자식노드' 이다.

 

코드

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

public class Main {
    static int[] ary;
    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());

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

        ary = new int[N+1];

        //트리의 높이 구하기
        int tree_height = (int) Math.ceil(Math.log(N)/Math.log(2));
        //2^(트리 높이+1)
        int tree_size = 1<<tree_height+1;
        tree = new long[tree_size];

        //리프노드일 경우 지점에 맞는 ary의 값을 가져와야 한다.
        for(int i=1;i<=N;++i){
            ary[i] = Integer.parseInt(br.readLine());
        }

        init(1, 1, N);
        StringBuilder sb = new StringBuilder();
        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());

            //b번째 수를 c로 바꾸기
            if(a==1){
                update(1,1, N, b, c);
            }

            //b부터 c까지의 곱 구하기
            if(a==2){
                long result = query(1, 1, N, b, c);
                sb.append(result).append('\n');
            }
        }

        System.out.println(sb);
    }



    //리프노드가 나올 때까지 재귀 호출을 시킨다.
    //나오면, 쌓인 재귀를 풀어가면서 부모~최상위노드까지 세그먼트 트리를 만든다.
    private static long init(int node, int start, int end) {
    	//*리프노드일 경우 배열의 그 수를 저장해야 한다.
        if(start==end)
            return tree[node] = ary[start];

        int mid = (start+end)/2;

		//*구간곱을 tree[node]에 저장해야 한다.
        return tree[node] = init(node*2,start, mid) * init(node*2+1,mid+1, end) % 1000000007;
    }

    private static long query(int node, int start, int end, int left, int right) {
        //범위 바깥이면
        //*&&가 아닌 ||이다.
        if(right<start || left>end)
            return 1;

        //구간 범위에 있으면
        if(left<=start && right>=end)
            return tree[node];

        int mid = (start+end)/2;

        long lval = query(node*2, start, mid, left, right);
        long rval = query(node*2+1, mid+1, end, left, right);

        //start, end 구간을 원하는 left, right에 맞춰가면서 구간곱 구하기
        return lval*rval % 1000000007;
    }

    private static void update(int node, int start, int end, int index, int change) {
        //*index가 구간을 벗어난 경우
        //바꿀 건 없다.
        if(index<start || index>end)
            return;

        //*리프노드를 찾을 때까지 계속 재귀 호출을 시킨다.
        //*찾으면 ary의 해당 인덱스 값과 그와 매칭되는 tree[node(리프노드)]를 변경해주고
        //*쌓여있던 재귀를 풀면서 부모노드~최상위노드(1)까지 차례대로 세그먼트 트리를 재구축한다.
        if(start==end) {
            ary[index] = change;
            tree[node] = change;
            return;
        }

        int mid = (start+end)/2;

        update(node*2, start, mid, index, change);
        update(node*2+1, mid+1, end, index, change);

        //*세그먼트 트리 재구축
        tree[node] = tree[node*2] * tree[node*2+1] % 1000000007;
    }
}