11505번

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

11505번: 구간 곱 구하기

이 문제는 세그먼트 트리를 구현하면 된다.

트리를 구간 곱으로 초기화하고, 리프노드를 바꿔야 할 때는 노드 갱신 메서드를 사용해서 바꿔서 계산해준다.

구간 곱을 계산하는 메서드를 구현하는 과정에서 처음에 구하려는 구간 곱의 범위 밖에 있는 경우에 리턴 값을 0으로 해서 구간 곱이 모두 0이 되어서 안되었다. 그래서 이유가 뭔가 생각했는데, 그림으로 이해하면 쉬울 것이다.

 

 

예를 들어 아래의 그림에서 구하려는 구간이 3~5라고하면, 2X3인 6에서 필요한건 3만이기 때문에 2 대신 1을 반환해야한다.

그래서 아래의 조건을 사용한다. 범위 외의 있는 곳은 0이 아닌 1을 반환하도록 해야 구할 수 있다. 0을 사용하면 3~5를 구간곱을 구하는 과정에서 3에서 반환되는 값이 0이기 때문에 0으로 나온다.

if(left>end || right<start){
    return 1;
}

그리고 범위에 있는 값이면 그 구간 곱을 반환하는 로직은 아래와 같은 조건으로 처리한다.

if(left<=start && right>=end){
    return tree[idx];
}

이에 대해서 세그트리로 왼쪽, 오른쪽 자식으로 나누어 들어가면서 구간 곱을 계산한다.

int mid = (start+end)/2;
return interval_multiple(start,mid,idx*2,left,right)*interval_multiple(mid+1,end,idx*2+1,left,right)%mod;

 

정답 코드는 아래와 같다.

package backjoon.b11505;

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

public class b11505 {
    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());
        long[] arr = new long[N+1];
        for(int i=1; i<=N; i++){
            arr[i] = Integer.parseInt(br.readLine());
        }//1 2 3 4 5
        tree t = new tree(N, arr);
        t.init(1,N,1);//tree 초기화
        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());//1: 바꾸려는 위치, 2:구간곱 시작 지점
            long c = Integer.parseInt(st.nextToken());//1: 바꾸려는 값, 2:구간곱 끝 지점
            if(a==1){
                t.update(1,N,1,b,c);//구간 변화
                t.arr[b]=c;
            }else {
                sb.append(t.interval_multiple(1,N,1,b,c)).append("\n");
            }
        }
        System.out.println(sb);
    }
}
class tree{
    final static long mod = 1000000007;
    long[] arr;
    long[] tree;
    int N;

    public tree(int n, long[] arr) {
        N = n;
        tree = new long[n*4];
        this.arr = arr;
    }

    public long init(int start, int end, int idx){
        if(start==end){
            return tree[idx]=arr[start];
        }
        int mid = (start+end)/2;
        return tree[idx]=init(start,mid,idx*2)*init(mid+1,end,idx*2+1)%mod;
    }
    public long interval_multiple(int start, int end, int idx, int left, long right){
        if(left>end || right<start){
            return 1;
        }
        if(left<=start && right>=end){
            return tree[idx];
        }
        int mid = (start+end)/2;
        return interval_multiple(start,mid,idx*2,left,right)*interval_multiple(mid+1,end,idx*2+1,left,right)%mod;
    }
    public void update(int start, int end, int idx, int what, long value){
        if(what<start || what>end){
            return;
        }

        if(start==end){
            tree[idx]=value;
            return;
        }

        int mid = (start+end)/2;

        update(start,mid,idx*2,what,value);
        update(mid+1,end,idx*2+1,what,value);

        tree[idx] = tree[2 * idx] * tree[2 * idx + 1]%mod;
    }
}