[자료구조] 백준 11505번: 구간 곱 구하기 (C++), 구간 곱 update함수

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

11505번: 구간 곱 구하기

이번 문제는 어떤 인덱스를 입력받은 값으로 바꿔주는 update가 많이 헷갈렸다.

세그먼트 트리 초기화 함수, 구간 곱 구하기 함수 같은 경우는 구간 합을 참고하여 구현할 수 있었지만

update부분은 구간 합 부분을 참고하면 오류가 난다.

 

[구간 합 업데이트]

void update(int start, int end, int node, int index, long long dif) {
	if (index < start || index > end) return;
	tree[node] += dif;
	if (start == end) return;
	int mid = (start + end) / 2;
	update(start, mid, node * 2, index, dif);
	update(mid + 1, end, node * 2 + 1, index, dif);
}

다음을 참고하여 구간 곱 업데이트를 구현해보았다.

 

[구간 곱 업데이트]

void update(int start, int end, int node, int index, int value) {
	if (index < start || index > end) return;
	sgTree[node] /= arr[index]; // Division By Zero?
	sgTree[node] *= value;
	//sgTree[node] %= MOD; // 나머지 정리 또한 성립 되지 않는다.
	if (start == end) return;
	int mid = (start + end) / 2;
	update(start, mid, node * 2, index, value);
	update(mid + 1, end, node * 2 + 1, index, value);
}

TC에서도 오류가 왜 발생하는지는 알 수 있었다.

5 2 2
1
2
3
4
5
1 3 0
2 2 5
1 3 6
2 2 5

다음 TC에서 발견할 수 있었다. 1 3 0 명령에서 3번째 인덱스 값이 0으로 업데이트되고, 2 2 5는 실행할 수 있으나

1 3 6 명령이 들어가면 기존의 인덱스 3의 값이 0이기 때문에

update함수의 순서대로

1) sgTree[node] /= arr[index]; -> 기존 세그먼트 트리에는 0이 들어가 있어서 기존 값 0으로 나눈다.

2) sgTree[node] *= arr[index]; -> 새로 들어올 값(6)을 곱해준다 -> 현재 세그먼트 트리 값이 0이라서 의미가 없다.

하지만, 이 오류가 일어나서 코드를 바꿔줘야 하는 건 알겠지만 왜 오류명이 Out Of Bounds인지는 알 수가 없었다.

 

여러 이유를 찾아보려 했다. (주석에 달아둔 내용들)

 

1) Division By Zero가 발생하는가?

>> 이미 세그먼트 트리 값이 0이라서 0을 0으로 나누는 오류는 발생하지 않는다. 만약 Division By Zero라면 Division By Zero라고 오류가 떴을 것이다.

 

2) 나머지 정리 규칙을 위반하는가?

>> 새로운 값을 곱해주면서 나머지 정리의 규칙을 위반하는 건가 생각해봤다. sgTree[node] /= arr[index]; 이 코드로 인해 나누기 연산이 있는데 나머지 정리가 성립하는 건가 생각해봤지만 sgTree[node] %= MOD; 부분을 주석하든 안 하든 똑같은 오류가 났다.

 

즉, 틀린 이유는 알겠으나 틀린 이유가 왜 Out Of Bounds인지는 파악을 할 수 없었다.

 

그렇다면 Update함수를 어떻게 고쳐줘야 작동하는가?

우선 나의 Update와 참고한 솔루션에서 제공하는 Update는 다른 접근을 가지는 것을 파악할 수 있었다.

나의 Update == 부모 노드부터 (위에서 아래로)

솔루션의 Update == 자식 노드부터 (아래에서부터 위로)

솔루션의 Update는 세그먼트 트리를 초기화시키듯이 leaf 노드부터 아예 값을 바꾸며 구간 곱들을 다시 계산했다.

>> 0이 곱할 값으로 입력이 되는 경우 때문에 leaf노드부터 아예 새로 갱신을 다시 해주어야 한다.

 

솔루션의 Update 함수를 바꿔줘도 Out Of Bounds가 발생한다.

>> Update 쪽에 문제가 아니었다는 걸 짐작할 수 있다.

>>>> 2시간 동안 본 끝에 문제에서는 N의 범위가 1,000,000 이하로 해줬지만 혹시나 하는 마음에 10,000,000로 잡으니 통과했다. (요즘 눈이 안 좋은가 의심했다.)

혹시 몰라서 질문 요청으로 데이터 개수에 대해 요청 글을 올려두었다.

 

>> (2021.12.10 추가 내용)

질문에 답이 왔다. 보자마자 내가 멍청하다고 생각했다. #define MAX 1000000 + 1로 정의를 해두고, 트리를 선언하면 연산자 우선순위로 인해서 1000000 + 1 * 4가 되어 1000004만큼 크기의 트리가 생성되기 때문에 그랬던 거였다. 보기 편하려고 저랬던 건데 앞으로 괄호도 달아주어야겠다.

 

[AC 코드] 

#include <iostream>
#define MAX (1000000 + 1)
#define MOD 1000000007
#define ll long long
using namespace std;

ll arr[MAX];
ll sgTree[MAX * 4];
int n, m, k;

ll sgInit(int start, int end, int node) {
	if (start == end) {
		return sgTree[node] = arr[start];
	}
	int mid = (start + end) / 2;
	return sgTree[node] = (((sgInit(start, mid, node * 2) % MOD) * 
		(sgInit(mid + 1, end, node * 2 + 1) % MOD))) % MOD;
}

ll update(int start, int end, int node, ll index, ll value) {
	if (index > end || index < start) return sgTree[node];
	if (start == end) {
		// Leaf 노드에 가서 아예 새로운 값을 할당해버림
		return sgTree[node] = value;
	}
	int mid = (start + end) / 2;
	return sgTree[node] = (((update(start, mid, node * 2, index, value) % MOD) *
		(update(mid + 1, end, node * 2 + 1, index, value) % MOD))) % MOD;
}

ll mul(int start, int end, int node, int left, int right) {
	if (left > end || right < start) return 1;
	if (left <= start && right >= end) {
		return sgTree[node];
	}
	int mid = (start + end) / 2;
	return (((mul(start, mid, node * 2, left, right) % MOD) * 
		(mul(mid + 1, end, node * 2 + 1, left, right) % MOD))) % MOD;
}

int main() {
	cin >> n >> m >> k;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
	}

	sgInit(1, n, 1);
	for (int i = 0; i < m + k; i++) {
		int a;
		cin >> a;
		ll b, c;
		cin >> b >> c;
		if (a == 1) {
			update(1, n, 1, b, c);
			arr[b] = c;
		}
		else {
			if (b > c) {
				ll temp = c;
				c = b;
				b = temp;
			}
			cout << mul(1, n, 1, b, c) % MOD << '\n';
		}
	}
	return 0;
}