백준 11505 : 구간 곱 구하기 (C++) [Segment tree]

 

  Segment tree에서 최소값, 최대값 구하는 것보다 조금은 더 생각해야 하는 것 같다.

 

**문제풀이 방법

- Tree 생성, 업데이트, query 연산(곱하기) 함수 작성

 

***코드

#include <stdio.h>
#include <math.h>
#include <vector>

#define denum 1000000007
#define MAX_N 1000001

typedef long long int ll;

using namespace std;

// start, end : node가 담당하고 있는 구간
// left, right : 계산을 하려는 구간

int N, M, K;
vector<ll>arr;
vector<ll>segment_tree;


// Segment tree 초기화
ll build_segment_tree(int node, int start, int end) {
	if (start == end) {
		return segment_tree[node] = arr[start] % denum;
	}
	else {		
		int left_child = node * 2;			// node의 왼쪽 자식
		int right_child = node * 2 + 1;		// node의 오른쪽 자식
		int mid = (start + end) / 2;

		ll left_result = build_segment_tree(left_child, start, mid) % denum;
		ll right_result = build_segment_tree(right_child, mid + 1, end) % denum;
		ll result = (left_result * right_result) % denum;

		segment_tree[node] = result;

		return segment_tree[node];
	}
}

// Tree update
ll update(int node, int start, int end, int idx, ll num) {
	if (idx < start || idx > end) return segment_tree[node];
	if (start == end) return segment_tree[node] = num;

	if (start != end) {  // leaf 노드가 아니면,
		int mid = (start + end) / 2;
		int left_child = node * 2;			// node의 왼쪽 자식
		int right_child = node * 2 + 1;		// node의 오른쪽 자식
		
		ll left_result = update(left_child, start, mid, idx, num) % denum;
		ll right_result = update(right_child, mid + 1, end, idx, num) % denum;
		ll result = (left_result * right_result) % denum;

		return segment_tree[node] = result;
	}
}

// 구간 곱 구하기
ll multiple(int node, int start, int end, int left, int right) {
	if (left > end || right < start) {  // 곱을 구하려는 구간이 node와 겹치지 않는 경우
		return 1;
	}
	if (left <= start && end <= right) { // node가 포함하는 구간이 합을 구하려는 구간에 속하는 경우 해당 node의 값 반환
		return segment_tree[node];
	}
	int mid = (start + end) / 2;
	int left_child = node * 2;			// node의 왼쪽 자식
	int right_child = node * 2 + 1;		// node의 오른쪽 자식

	ll left_result = multiple(left_child, start, mid, left, right) % denum;
	ll right_result = multiple(right_child, mid + 1, end, left, right) % denum;
	ll result = (left_result * right_result) % denum;
	return result;
}


int main() {
	//freopen("input.txt", "r", stdin);

	scanf("%d %d %d", &N, &M, &K);

	arr.clear();
	segment_tree.clear();

	int tree_Height = (int)ceil(log2(N));
	int tree_Size = (1 << (tree_Height + 1));
	segment_tree.resize(tree_Size);

	M += K;		//M번 update와 K번 구간곱을 구하므로 총연산 횟수는 M+K

	// 값 입력받기
	for (int i = 0; i < N; i++) {
		ll value;
		scanf("%lld", &value);
		arr.emplace_back(value);
	}

	build_segment_tree(1, 0, N - 1);

	while (M--) {
		int a;
		scanf("%d", &a);
		if (a == 1) {	// a==1이면 b번째 수를 c로 바꾸기
			int b;
			ll c;
			scanf("%d %lld", &b, &c);
			b -= 1;
			ll num = c;
			update(1, 0, N - 1, b, num);
		}
		else if (a == 2) {	// a==2이면 구간곱 구하기
			int b, c;
			scanf("%d %d", &b, &c);
			b--;	// index가 0부터 시작하므로 1 빼주기
			c--;	// index가 0부터 시작하므로 1 빼주기

			ll result = multiple(1, 0, N - 1, b, c);

			printf("%lld\n",result);
		}
	}

	return 0;
}

 

****주의할 점

- 새로운 값 업데이트 할 때, 따로 연산 필요없이 바로 값 대입 - 모듈러 연산 주의(곱의 법칙 이용) - 자료형 주의 - 연산하려는 구간이 노드의 포함 범위 밖일 경우 '최소값' '최대값' 문제(0 반환)와는 다르게 '1'을 반환해야함

 

<Reference>

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

- https://yabmoons.tistory.com/453