[BOJ 11505] 구간 곱 구하기 (Java)

문제

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

11505번: 구간 곱 구하기

 

풀이

구간 합 구하기와 비슷한 풀이다. 

2021.12.06 - [Problem Solving/BOJ] - [BOJ 2042] 구간 합 구하기 (Java)

[BOJ 2042] 구간 합 구하기 (Java)

 

Segment Tree를 만들어서 구간곱을 초기화 한 후, 특정 인덱스의 수를 변경하거나 특정 구간곱을 구해서 출력한다.

각 함수 별로 mod 연산을 빠짐없이 잘 해주어야 한다.  

특히 update같은 경우, leaf 노드 부터 차례대로 업데이트 해줘야 한다. 

각 node를 별도로 update를 해버리면 mod 연산이 제대로 적용되지 않는 것으로 판단된다. 

 

잘못된 Update 코드 (4 % 에서 틀림)

    public static void update(int start, int end, int target, int from, int to, int node){
        if(target < start || target > end ) return;
        tree[node] = (from == 0)? to : (tree[node]/from*to)%mod;
        if(start == end) return;
        int mid = (start+end)/2;
        update(start, mid, target, from, to, node*2);
        update(mid+1, end, target, from, to, node*2+1);
    }

 

예제

5 2 2
1
2
3
4
5
1 3 6
2 2 5
1 5 2
2 3 5

1. 구간곱 세그먼트 트리 생성

    public static long init(int start, int end, int node){
        if(start == end) return tree[node] = arr[start];
        int mid = (start + end)/2;
        return tree[node] = (init(start, mid, node*2) * init(mid+1, end, node*2+1))% mod;
    }

 

구간곱 세그먼트 트리

2. 특정 Index의 수 변경

해당 index를 포함하는 구간곱 노드 중 가장 leaf node 부터 계산 

해당 index를 포함하는 구간곱을 이전 수로 나눈 후 변경하려는 수를 곱해준다. 

이전 수가 0일 경우 예외 처리도 추가해주었다.

    public static long update(int start, int end, int target, int from, int to, int node){
        if(target < start || target > end ) return tree[node];
        if(start == end){
            tree[node] = (from == 0)? to : (tree[node]/from*to) % mod;
            return tree[node];
        }
        int mid = (start+end)/2;
        return tree[node] = (update(start, mid, target, from, to, node*2) * update(mid+1, end, target, from, to, node*2+1)) % mod;
    }

3번째 수를 6으로 변경

3. 특정 구간 곱 구하기

특정 구간곱 범위 내에 있는 구간곱 노드를 모두 곱해준다.

범위 밖에 있다면 1을 리턴한다.

 

    public static long multiply(int start, int end, int left, int right,  int node){
        if(left > end || right < start) return 1;
        if(left <= start && end <= right) return tree[node];
        int mid = (start + end)/2;
        return (multiply(start, mid, left, right, node*2) * multiply(mid+1, end, left, right, node*2+1)) % mod;
    }

 

2~5 구간곱 구하기 (2 * 6 * 20) = 240

소스코드

package segmenttree;

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

public class BOJ11505 {

    public static int[] arr;
    public static long[] tree;
    public static int mod = 1000000007;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken()); // 수의 개수
        int M = Integer.parseInt(st.nextToken()); // 수의 변경이 일어난 횟수
        int K = Integer.parseInt(st.nextToken()); // 구간의 곱을 구하는 횟수

        // 수를 저장할 배열
        arr = new int[N+1];
        for(int i = 1; i <= N; i++){
            arr[i] = Integer.parseInt(br.readLine());
        }

        // 구간 곱 세그먼트 트리 생성
        tree = new long[N*4];
        init(1, N, 1);

        for(int i = 0; i < M+K; i++){
            st = new StringTokenizer(br.readLine());
            int flag = Integer.parseInt(st.nextToken());
            if(flag == 1){
                // 수를 변경하기
                int target = Integer.parseInt(st.nextToken());
                int from = arr[target];
                int to = Integer.parseInt(st.nextToken());
                update(1, N, target, from , to, 1);
                arr[target] = to;
            } else {
                // 구간의 곱 구하기
                int left = Integer.parseInt(st.nextToken());
                int right = Integer.parseInt(st.nextToken());
                bw.write(multiply(1, N, left, right, 1) + "\n");
            }
        }
        bw.flush();
    }

    public static long update(int start, int end, int target, int from, int to, int node){
        if(target < start || target > end ) return tree[node];
        if(start == end){
            tree[node] = (from == 0)? to : (tree[node]/from*to) % mod;
            return tree[node];
        }
        int mid = (start+end)/2;
        return tree[node] = (update(start, mid, target, from, to, node*2) * update(mid+1, end, target, from, to, node*2+1)) % mod;
    }

    public static long multiply(int start, int end, int left, int right,  int node){
        if(left > end || right < start) return 1;
        if(left <= start && end <= right) return tree[node];
        int mid = (start + end)/2;
        return (multiply(start, mid, left, right, node*2) * multiply(mid+1, end, left, right, node*2+1)) % mod;
    }

    public static long init(int start, int end, int node){
        if(start == end) return tree[node] = arr[start];
        int mid = (start + end)/2;
        return tree[node] = (init(start, mid, node*2) * init(mid+1, end, node*2+1)) % mod;
    }
}