[JAVA/백준] 11505번: 구간 곱 구하기

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
import java.util.*;
import java.io.*;
/**
 * @author HEESOO
 *
 */
class Main {
	static int[] input;
	static long[] tree;
	static int MOD;
	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());
		
		input=new int[n+1];
		tree=new long[n*4];	
		MOD=1000000007;
		for(int i=1;i<=n;i++) {
			st=new StringTokenizer(br.readLine());
			input[i]=Integer.parseInt(st.nextToken());
		}
		
		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());
			int c=Integer.parseInt(st.nextToken());
			if(a==1) {
				input[b]=c;
				update(1, 1, n, b,  c);
			}
			else {
				System.out.println(sum(1, 1, n, b, c));
			}
		}
	}
	
	public static long init(int node, int left, int right) {
		if(left==right) return tree[node]=input[left];		
		
		int mid=(left+right)/2;
		return tree[node]=init(node*2, left, mid)*init(node*2+1, mid+1, right)%MOD;
	}
	
	public static long update(int node, int left, int right, int idx, int c) {
		// 세그먼트 트리 덧셈과 달리 리프노드에서 루트로 올라가며(재귀) 업데이트
		if(idx<left || idx>right) return tree[node]; // 갱신할 값이 포함된 범위가 아닐 경우	
		if(left==right) return tree[node]=c; // 리프노드
		
		// 자식의 값을 이용해 갱신
		int mid=(left+right)/2;
		return tree[node]=update(node*2, left, mid, idx, c)*update(node*2+1, mid+1, right, idx, c)%MOD;
	}
	
	public static long sum(int node, int left, int right, int rangeA, int rangeB) {
		if(right<rangeA || left>rangeB) return 1; // 범위 초과
		if(rangeA<=left && right<=rangeB) return tree[node]; // 범위 안에 속함
		
		// 범위에 걸쳐 있는 경우 자식으로 내려가며 범위 좁히기
		int mid=(left+right)/2;
		return sum(node*2, left, mid, rangeA, rangeB)*sum(node*2+1, mid+1, right, rangeA, rangeB)%MOD;
		
	}
	
}