백준 11505번 구간 곱 구하기 C++ / 세그먼트 트리

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

 

우선 세그먼트 트리 이해 후 한번에 풀이 성공했다.

다만 좀 헷갈렸던 부분은 배열을 인덱스 0부터가 아니라 1부터 사용하는거라 트리쪽도 매개변수를 어떻게 넣어야 할지 잠시 고민했다.

근데 그냥 배열 index 1부터 입력받게 하니까 트리는 원래 index 1부터 쓰는거라 별 다르게 바꿀것 없이

0 ~ N - 1로 범위 지정할거를 1 ~ N으로 지정해주면 그만이었다.

 

정답코드)

#include <bits/stdc++.h>
using namespace std;

vector<int> arr;
vector<long long> SegmentTree;

void Make_SegmentTree(int Node, int Start, int End) 
{
	if (Start == End) SegmentTree[Node] = arr[Start];
	else {
		Make_SegmentTree(Node * 2, Start, (Start + End) / 2);
		Make_SegmentTree(Node * 2 + 1, (Start + End) / 2 + 1, End);
		SegmentTree[Node] = (SegmentTree[Node * 2] * SegmentTree[Node * 2 + 1]) % 1000000007;
	}
}

void Update_SegmentTree(int Node, int Start, int End, int Index, int Value) {
	if (Index < Start || Index > End) return;
	if (Start == End) {
		arr[Index] = Value;
		SegmentTree[Node] = Value;
		return;
	}

	Update_SegmentTree(Node * 2, Start, (Start + End) / 2, Index, Value);
	Update_SegmentTree(Node * 2 + 1, (Start + End) / 2 + 1, End, Index, Value);
	SegmentTree[Node] = (SegmentTree[Node * 2] * SegmentTree[Node * 2 + 1]) % 1000000007;
}

long long Multiple(int Node, int Start, int End, int Left, int Right) {
	if (Left > End || Right < Start) return 1;
	if (Left <= Start && End <= Right) return SegmentTree[Node];

	int Mid = (Start + End) / 2;
	long long Left_Result = Multiple(Node * 2, Start, Mid, Left, Right);
	long long Right_Result = Multiple(Node * 2 + 1, Mid + 1, End, Left, Right);
	return (Left_Result * Right_Result) % 1000000007;
}

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

	int N, M, K;
	cin >> N >> M >> K;

	// 입력받고
	arr.resize(N + 1, 0);
	for (int i = 1; i < N + 1; i++) {
		cin >> arr[i];
	}

	// 세그먼트트리 만들고
	int Tree_Height = (int)ceil(log2(N));
	int Tree_Size = (1 << (Tree_Height + 1));
	SegmentTree.resize(Tree_Size);
	Make_SegmentTree(1, 1, N);

	// 요청받고
	int a, b, c;
	for (int i = 0; i < M + K; i++) {
		cin >> a >> b >> c;

		if (a == 1) {
			// b번째수를 c로 변경
			Update_SegmentTree(1, 1, N, b, c);
		}
		else if (a == 2) {
			// b부터 c까지의 곱을 출력
			cout << Multiple(1, 1, N, b, c) << '\n';
		}
	}

	return 0;
}