[BOJ/Segment Tree] 백준 11505 - 구간 곱 구하기 (Java)

백준 11505 - 구간 곱 구하기

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

문제

입력
첫째 줄: 수의 개수 N (1 <= N <= 1,000,000)
, 수의 변경이 일어나는 횟수 M (1 <= M <= 10,000), 구간의 곱을 구하는 횟수 K (1 <= K <= 10,000)
둘째 줄 ~ N + 1번째 줄: N개의 수
N + 2번째 줄 ~ N + M + K + 1번째 줄: 세 개의 정수 a, b, c
a가 1인 경우 b번째 수를 c로 바꾸고 a가 2인 경우에는 b번째 수부터 c번째 수까지의 곱 구하여 출력
출력: 첫째 줄부터 K줄에 걸쳐 구한 구간의 곱 % 1,000,000,0007

---

풀이

트리 생성: `arr` 배열 기반으로 세그먼트 트리 한 번 만들어두는 함수

• `arr = new long[N + 1]`: 실제 배열 값
• `tree = new long[4 * N]`: 세그먼트 트리 -> 구간 곱 저장

static void init(int node, int start, int end) {
    if (start == end) {
        tree[node] = arr[start] % MOD;
        return;
    }

    int mid = (start + end) / 2;
    init(node * 2, start, mid);
    init(node * 2 + 1, mid + 1, end);
    tree[node] = (tree[node * 2] * tree[node * 2 + 1]) % MOD;
}

 

값 변경:`idx`번째 값 ->`val`로 변경

• 리프에서 값을 직접 바꾸고 올라오면서 다시 계산
• 범위 밖(`idx < start || idx > end`): 현재 구간에 `idx 없음 => 무시
• 리프 도착(`start == end`): `tree[node] = val % MOD`
• 내부 노드 갱신: `tree[node] = (lt * rt) % MOD`

static void update(int node, int start, int end, int idx, long val) {
    if (idx < start || idx > end) return;

    if (start == end) {
        tree[node] = val % MOD;
        return;
    }

    int mid = (start + end) / 2;
    update(node * 2, start, mid, idx, val);
    update(node * 2 + 1, mid + 1, end, idx, val);
    tree[node] = (tree[node * 2] * tree[node * 2 + 1]) % MOD;
}

 

query: 구간 [lt, rt] 곱

• 완전히 벗어남: `rt < start || end < lt`
• 완전히 포함: `lt <= start && end <= rt`
• 일부만 겹침: `return (query(lt) * query(rt)) % MOD`

static long query(int node, int start, int end, int lt, int rt) {
    if (rt < start || end < lt) return 1;
    if (lt <= start && end <= rt) return tree[node];

    int mid = (start + end) / 2;
    return (query(node * 2, start, mid, lt, rt)
            * query(node * 2 + 1, mid + 1, end, lt, rt)) % MOD;
}

 

---

코드

import java.io.*;
import java.util.*;

// 구간 곱 구하기
public class boj_11505 {
    static int N, M, K;
    static long[] arr, tree;
    static final long MOD = 1_000_000_007L;

    static void init(int node, int start, int end) {
        if (start == end) {
            tree[node] = arr[start] % MOD;
            return;
        }

        int mid = (start + end) / 2;
        init(node * 2, start, mid);
        init(node * 2 + 1, mid + 1, end);
        tree[node] = (tree[node * 2] * tree[node * 2 + 1]) % MOD;
    }

    static void update(int node, int start, int end, int idx, long val) {
        if (idx < start || idx > end) return;

        if (start == end) {
            tree[node] = val % MOD;
            return;
        }

        int mid = (start + end) / 2;
        update(node * 2, start, mid, idx, val);
        update(node * 2 + 1, mid + 1, end, idx, val);
        tree[node] = (tree[node * 2] * tree[node * 2 + 1]) % MOD;
    }

    static long query(int node, int start, int end, int lt, int rt) {
        if (rt < start || end < lt) return 1;
        if (lt <= start && end <= rt) return tree[node];

        int mid = (start + end) / 2;
        return (query(node * 2, start, mid, lt, rt)
                * query(node * 2 + 1, mid + 1, end, lt, rt)) % MOD;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

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

        arr = new long[N + 1];
        tree = new long[4 * N];

        for (int i = 1; i <= N; i++) {
            arr[i] = Long.parseLong(br.readLine());
        }

        init(1, 1, N);

        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());
            long c = Long.parseLong(st.nextToken());

            if (a == 1) update(1, 1, N, b, c);
            else sb.append(query(1, 1, N, b, (int) c)).append('\n');
        }

        System.out.println(sb);
    }
}