073 : 구간 곱 구하기

(Briefing)
(문제)	(단 하나의 맥락)	(입출력과 되어야 하는 그림)
N개의 수 수의 변경이 빈번히 일어나는 와중에 특정 구간의 곱을 구함	세그먼트 트리 + MOD	I // 수의 갯수 N, 변경횟수 M, 곱 구하는 횟수 K (2) 첫번째 수 ... (N+1) N번쨰 수 (N+2) a b c ... (N + M + K + 1) a b c O // K개의 줄에 결과를 1000000007로 나눈 나머지를 출력

*a가 1일 때 b번째 수를 c로 바꿈

*a가 2일 때 b~c 곱 출력

 

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

public class Main {

    // B.r
    static long[] tree;

    // P.r
    static int MOD;

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

        // ISC
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

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

        int treeHeight = 0;
        int length = N;
        while (length != 0) {
            length /= 2;
            treeHeight++;
        }

        int treeSize = (int) Math.pow(2, treeHeight + 1);
        int leftNodeStartIndex = treeSize / 2 - 1;
        MOD = 1000000007;
        
        // B.r
        tree = new long[treeSize + 1];
        for (int i = leftNodeStartIndex + 1; i <= leftNodeStartIndex + N; i++) {
            tree[i] = Long.parseLong(br.readLine());
        }
        
        // Operating setTree
        setTree(treeSize - 1);
        
        for (int i = 0; i < M + K; i++) {
            st = new StringTokenizer(br.readLine());
            long a = Long.parseLong(st.nextToken());
            int s = Integer.parseInt(st.nextToken());
            long e = Long.parseLong(st.nextToken());
            
            // Operating changeVal & pMul + OEC
            if (a == 1) {
                changeVal(leftNodeStartIndex + s, e);
            } else if (a == 2) {
                s = s + leftNodeStartIndex;
                e = e + leftNodeStartIndex; 
                System.out.println(pMul(s, (int) e));
            }
        }
        br.close();
    }
    
    // External Module setTree
    private static void setTree(int i) {
        while (i != 1) {
            tree[i/2] = tree[i/2] * tree[i] % MOD;
            i--;
        }
    }
    
    // External Module : changeVal
    private static void changeVal(int index, long val) {
        tree[index] = val;
        while (index > 1) {
            index = index / 2;
            tree[index] = tree[index*2] % MOD *tree[index*2 + 1] % MOD;
        }
    }
    
    // External Module : pMul
    private static long pMul(int s, int e) {
        long pMul = 1;
        while (s <= e) {
            if (s % 2 == 1) {
                pMul = pMul * tree[s] % MOD;
                s++;
            }
            if (e % 2 == 0) {
                pMul = pMul * tree[e] % MOD;
                e--;
            }
            s = s / 2;
            e = e / 2;
        }
        return pMul;
    }
}