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

www.acmicpc.net/problem/11505

11505번: 구간 곱 구하기

구간의 곱을 나타내는 세그먼트 트리를 만들고 세그먼트 트리의 쿼리와 업데이트를 이용해 문제를 해결했다. 세그먼트 트리를 나타내는 배열의 크기를 넉넉하게 n*4로 설정했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int n, m, k;
vector<int> input_data;
vector<int> sgmtt;

//세그먼트 트리 만들기
long long Makesgmtt(int here, int range_left, int range_right)
{
	if (range_left == range_right)
		return sgmtt[here] = input_data[range_left];

	int mid = (range_left + range_right) / 2;
	int left_child = here * 2 + 1;
	int right_child = here * 2 + 2;

	return sgmtt[here] = (Makesgmtt(left_child, range_left, mid) * Makesgmtt(right_child, mid + 1, range_right) + 1000000007) % 1000000007;
}

//세그먼트 트리 업데이트
long long Updatesgmtt(int here, int range_left, int range_right, int pos, int new_value)
{
	if (range_left == range_right && range_right == pos)
		return sgmtt[here] = new_value;

	if (pos < range_left || range_right < pos)
		return sgmtt[here];

	int mid = (range_left + range_right) / 2;
	int left_child = here * 2 + 1;
	int right_child = here * 2 + 2;

	return sgmtt[here] = (Updatesgmtt(left_child, range_left, mid, pos, new_value)*Updatesgmtt(right_child, mid + 1, range_right, pos, new_value) + 1000000007) % 1000000007;
}

//세그먼트 트리 쿼리
long long Querysgmtt(int here, int range_left, int range_right, int find_left, int find_right)
{
	if (find_right < range_left || range_right < find_left)
		return 1;

	if (find_left <= range_left && range_right <= find_right)
		return sgmtt[here];

	int mid = (range_left + range_right) / 2;
	int left_child = here * 2 + 1;
	int right_child = here * 2 + 2;

	return (Querysgmtt(left_child, range_left, mid, find_left, find_right) * Querysgmtt(right_child, mid + 1, range_right, find_left, find_right) + 1000000007) % 1000000007;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n >> m >> k;

	for (int i = 0; i < n; i++)
	{
		int input;
		cin >> input;

		input_data.push_back(input);
	}

	sgmtt.resize(n * 4); //세그먼트 트리를 나타내는 배열의 크기를 넉넉하게 n*4로 설정한다.
	
	Makesgmtt(0, 0, n - 1);

	for (int i = 0; i < m + k; i++)
	{
		int a, b, c;

		cin >> a >> b >> c;

		if (a == 1)
		{
			Updatesgmtt(0, 0, n - 1, b - 1, c);
		}

		if (a == 2)
		{
			cout << Querysgmtt(0, 0, n - 1, b - 1, c - 1) << "\n";
		}
	}

	return 0;
}