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

🔗 문제 링크

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

✍️ 문제 풀이

해당 문제는 수열의 특정 구간 곱을 구하는 문제로, 세그먼트 트리 알고리즘을 사용하여 풀이했다.

1) 수열을 저장할 datas, 구간합 트리를 저장할 tree 배열을 선언한다. 이 때 구간합 트리의 크기는 수열 배열의 최대 크기의 4배 이상으로 설정한다.

2) 수의 개수 n과 수의 변경이 일어나는 횟수 m, 구간 곱을 구하는 횟수 k 를 입력 받아 저장하고, n개의 수를 입력받아 datas에 저장한다.

3) init() 함수를 통해 구간합 트리를 초기화 한다.

• 최상위 노드부터 시작해 데이터 범위를 반씩 분할하여 구간곱을 저장하는 방식으로 트리를 채운다. 재귀를 통해 가장 작은 범위의 값을 구해, 그 값들로 더 큰 범위의 값을 구한다.
• 현재 순서 노드의 값 = 왼쪽 자식 노드의 값 * 오른쪽 자식 노드의 값
• 더 이상 분할할 수 없을 때(범위 내에 수가 하나 뿐일 때) 해당 수를 현재 순서 노드의 값으로 설정하고 반환한다.

4) m + k 만큼의 (곱 구하기, 수 바꾸기)를 실행한다.

• mul() 함수를 통해 현재 순서에서 구해야하는 범위의 구간합을 구하고 이를 출력한다.
  • 범위 밖에 있는 경우 1을 반환한다.
  • 범위 안에 있는 경우 현재 순서 노드의 구간곱을 반환한다.
  • 범위에 걸쳐 있는 경우 현재 범위의 절반으로 나누어 각 범위에 대해 mul()을 실행한다.
• update() 함수를 통해 특정 인덱스의 수를 다른 수로 변경한다.
  • 구간합과 달리 특정 노드의 값이 0으로 바뀌거나, 0에서 다른 값으로 바뀔 때 상위 노드부터 계산해 값을 수정할 수 없다. 따라서 init()과 같이 하위 노드 값부터 상위 노드로 바뀌는 방식으로 진행한다.
  • 범위 밖에 있는 경우 무시한다.
  • 범위 안에 있다면
    • 더 이상 분할할 수 없을 때(범위 내에 수가 하나 뿐일 때)는 바뀔 수(dif)를 현재 순서 노드의 값으로 설정하고 반환한다.
    • 분할할 수 있다면 데이터 범위를 반으로 분할해 각 범위에 대해 update()를 실행한다.
  • update() 함수 실행 이후 datas의 특정 인덱스 값도 변경해주어야 한다.

🖥️ 풀이 코드

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

int n, m, k;
long long tree[4000004];
long long datas[1000001];
const long long MOD = 1000000007;

// 구간곱 트리 초기화
long long init(int start, int end, int node)
{
	if (start == end) return tree[node] = datas[start];
	int mid = start + (end - start) / 2;
	return tree[node] = (init(start, mid, node * 2) * init(mid + 1, end, node * 2 + 1)) % MOD;
}

// 구간곱 구하기
long long mul(int start, int end, int node, int left, int right)
{
	if (end < left || right < start) return 1;
	if (left <= start && end <= right) return tree[node];
	int mid = start + (end - start) / 2;
	return (mul(start, mid, node * 2, left, right)
		* mul(mid + 1, end, node * 2 + 1, left, right)) % MOD;
}

// 특정 수 변경
long long update(int start, int end, int node, int index, long long dif)
{
	if (index < start || end < index) return tree[node];
	if (start == end) return tree[node] = dif;	// index가 현재 구간에 들어오고, 구간 내에 수가 하나 뿐이다 -> 해당 수가 바꾸고자 하는 수이므로 해당 노드 값 변경 
	int mid = start + (end - start) / 2;
	return tree[node] = (update(start, mid, node * 2, index, dif) * update(mid + 1, end, node * 2 + 1, index, dif)) % MOD;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);

	cin >> n >> m >> k;
	for (int i = 1; i <= n; i++)
		cin >> datas[i];

	init(1, n, 1);
	for (int i = 0; i < m + k; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		if (a == 1)
		{
			update(1, n, 1, b, c);
			datas[b] = c;
		}
		else
			cout << mul(1, n, 1, b, c) << '\n';
	}
}