BOJ : 11505 구간 곱 구하기

---

[BOJ 11505(G1)리뷰]

N개의 값이 1번 index부터 차례대로 주어진다. 그 후에 명령을 입력받는데 "1 a b"의 형태라면 a를 b라는 수로 바꿔야하고, "2 a b"의 형태라면 a번 index부터 b번 index까지의 곱을 출력해야 한다.

값을 update하는 작업이 있으므로 단순히 구간의 곱을 저장하는 것으로는 시간내에 해결 할 수 없다.

따라서 값을 update하고 구하는 과정을 O(logN)에 수행할 수 있는 세그먼트 트리 자료구조를 이용했다.

일반적으론 구간의 합을 세그먼트 트리 구조로 저장하지만, 이번 문제는 구간의 곱을 저장해주면 된다. 따라서 값에 영향을 주지 않도록 비어있는 노드는 1로 초기화 해주어야하며, 값을 update할때는 botoom-up방식으로 구현 하는 것이 깔끔하다.

/*
	21.01.16
	BOJ : 11505 구간 곱 구하기 (https://www.acmicpc.net/problem/11505)
	자료구조/세그먼트 트리
*/
#include <bits/stdc++.h>
using namespace std;

#define ll long long int
#define MAX 1000000007
ll* tree;
ll* nums;
int S;
int N, M,K;

void init() {
	for (int i = S; i < 2 * S; i++) {
		if (i - S + 1 <= N) {
			tree[i] = nums[i-S+1];
		}
		else {
			tree[i] = 1;
		}
	}

	for (int i = S - 1; i >= 1; i--) {
		tree[i] = (tree[i * 2] * tree[i * 2 + 1]) % MAX;
	}
}

ll query(int node, int l, int r, int ql, int qr) {
	if (l > qr || r < ql) return 1;
	else if (l >= ql && r <= qr) return tree[node];
	else {
		int mid = (l + r) / 2;
		return (query(node * 2, l, mid, ql, qr) * query(node * 2 + 1, mid + 1, r, ql, qr)) % MAX;
	}
}


void update(int node,int newValue) {
	nums[node] = newValue;
	node = S + node - 1;
	tree[node] = newValue;
	while (node >= 1) {
		node /= 2;
		tree[node] = (tree[node * 2] * tree[node * 2 + 1]) % MAX;
	}
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(0);
	
	
	cin >> N >> M >> K;

	nums = new ll[N + 1];

	for (int i = 1; i <= N; i++)
	{
		cin >> nums[i];
	}

	S = ceil(log2(N));
	S = (1 << S);

	tree = new ll[2 * S] ;

	init();

	for (int i = 0; i < M + K; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		if (a == 1) {
			update(b, c);
		}
		else if (a == 2) {
			cout << query(1, 1, S, b, c)<<'\n';
		}
	}

	return 0;
}