백준 11505: 구간 곱 구하기

문제 요약

어떤 N개의 수가 주어져 있다. 그런데 중간에 수의 변경이 빈번히 일어나고 그 중간에 어떤 부분의 곱을 구하려 한다. 만약에 1, 2, 3, 4, 5 라는 수가 있고, 3번째 수를 6으로 바꾸고 2번째부터 5번째까지 곱을 구하라고 한다면 240을 출력하면 되는 것이다. 그리고 그 상태에서 다섯 번째 수를 2로 바꾸고 3번째부터 5번째까지 곱을 구하라고 한다면 48이 될 것이다.

문제 분류

• 자료 구조
• 세그먼트 트리

문제 풀이

세그먼트 트리의 이전 포스트 [C++] 백준 2042: 구간 합 구하기와는 다른 방법으로 구현해보았다. 이전 포스트에서는 미리 리프노드의 인덱스를 구하고, 이를 이용하여 구축 및 수정하는 방법을 사용하였다.

반면에 이번 코드에서는 재귀호출을 적극적으로 사용함으로써 리프노드의 인덱스를 굳이 알 필요가 없어졌다. 즉, log2()나 pow()혹은 시프트 연산자(<<)를 사용하지 않아도 되었다.

구현은 역시 루트노드를 0번 인덱스로 삼았다. 구축 및 수정에서 재귀호출을 사용하였고, 실제 구간곱을 구하는 과정에서 예외의 경우 0이 아닌 1로 처리해주었다. 곱셈에서 1을 사용하여야 자기자신이 나온다.

long을 사용하여도 충분히 풀 수 있다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>

using namespace std;

long n, a[1000000], seg[4000000];

long construct(int start, int end, int idx)
{
	if (start == end) {
		seg[idx] = a[start];
		return seg[idx];
	}
	int mid = (start + end) / 2;
	seg[idx] = (construct(start, mid, idx * 2 + 1) * construct(mid + 1, end, idx * 2 + 2)) % 1000000007;

	return seg[idx];
}

long update(int l, int r, int idx, int loc, int val)
{
	if (loc < l || loc > r) return seg[idx];
	if (l == r) {
		if(l == loc) seg[idx] = val;
		return seg[idx];
	}
	int mid = (l + r) / 2;
	seg[idx] = (update(l, mid, idx * 2 + 1, loc, val) * update(mid + 1, r, idx * 2 + 2, loc, val)) % 1000000007;
	return seg[idx];
}

long mul(int l, int r, int il, int ir, int idx)
{
	if (l > ir || r < il) return 1;
	if (il <= l && ir >= r) return seg[idx];
	int mid = (l + r) / 2;
	return (mul(l, mid, il, ir, idx * 2 + 1) * mul(mid + 1, r, il, ir, idx * 2 + 2)) % 1000000007;
}

int main()
{
	int m, k, in1, in2, in3;
	scanf("%d%d%d", &n, &m, &k);
	for (int i = 0; i < n; i++)
		scanf("%d", a + i);
	construct(0, n - 1, 0);
	for (int i = 0; i < m + k; i++) {
		scanf("%d%d%d", &in1, &in2, &in3);
		in2--;
		if (in1 == 1)
			update(0, n - 1, 0, in2, in3);
		else
			printf("%ld\n", mul(0, n - 1, in2, in3 - 1, 0));
	}
	return 0;
}

후일담

찾아보니 세그먼트 트리의 경우 입력된 배열의 크기보다 4배의 크기를 할당하는 것이 보편적인 것 같다.