[BAE/<JOON> 문제풀이] 11505. 구간 곱 구하기

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

11505번: 구간 곱 구하기

핵심::
세그 트리에서 Update 함수 부분 수정

풀이::
합이나 최소값을 구하는 문제와 다른 점은 Update를 할 때 Bottom-Up 방식으로 해야한다.

합이나 최소값 비교는 순서와 상관 없이 부모 노드만 있어도 쉽게 역연산 ( 더하기 )을 수행할 수 있지만

곱셈의 경우에는 나누고 다시 곱하는 역연산이 필요한데, 값이 매우 크므로 부모노드에 연산되어있는 나머지 값으로는 해당 역연산이 불가능하다.

따라서 리프 노드에 도달한 이 후 거슬러 올라가며 부모 노드에 값 업데이트를 진행한다.

의견::
최대값 최소값 구하는 문제보다 Update하는 로직이 많이 변경되어서 헷갈렸다.

코드::

//backjoon
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>

using namespace std;

const long long cc = 1000000007;
int n, m, k;

// a: 배열 a
// tree: 세그먼트 트리
// node: 세그먼트 트리 노드 번호
// node가 담당하는 합의 범위가 start ~ end
long long init(vector<long long>& a, vector<long long>& tree, int node, int start, int end) {
	if (start == end) {
		return tree[node] = a[start];
	}
	else {
		return tree[node] = init(a, tree, node * 2, start, (start + end) / 2) * init(a, tree, node * 2 + 1, (start + end) / 2 + 1, end) % cc;
	}
}

// node가 담당하는 구간이 start~end이고, 구해야하는 합의 범위는 left~right
long long mul(vector<long long>& tree, int node, int start, int end, int left, int right) {
	if (left > end || right < start) {
		return 1;
	}
	if (left <= start && end <= right) {
		return tree[node];
	}
	return mul(tree, node * 2, start, (start + end) / 2, left, right) * mul(tree, node * 2 + 1, (start + end) / 2 + 1, end, left, right) % cc;
}

//트리 구조로 되어있기 때문에 최대 log(n)의 변환으로 필요한 값들을 모두 변경 할 수 있다.
long long update(vector<long long>& tree, int node, int start, int end, int index, long long next) {
	if (index < start || index > end) return tree[node]; // 범위를 벗어난 노드라면 계산 없이 값반환 
	long long l = 1, r = 1;
	if (start != end) { // Leaf Node 가 아니라면 아래값 계산
		l = update(tree, node * 2, start, (start + end) / 2, index, next);
		r = update(tree, node * 2 + 1, (start + end) / 2 + 1, end, index, next);
		return tree[node] = (l * r) % cc;
	}
	else return tree[node] = next;	// Leaf Node 라면 해당 값 반환 
}

int main()
{
	cin >> n >> m >> k;
	m += k;
	vector<long long> arr(n + 1);
	vector<long long> sgtree(2 << (int)ceil(log2(n)));
	for (int i = 1; i <= n; i++) {
		scanf("%lld", &arr[i]);
	}
	init(arr, sgtree, 1, 1, n);

	for (int i = 1; i <= m; i++) {
		long long inst;
		int a, b;
		scanf("%lld %d %d", &inst, &a, &b);
		if (inst == 1) {
			long long imsi = arr[a];
			arr[a] = b;
			update(sgtree, 1, 1, n, a, b);
		}
		if (inst == 2) {
			printf("%lld\n", mul(sgtree, 1, 1, n, a, b));
		}
	}

	return 0;
}