[알고리즘] 구간 곱 구하기

구현 방식

• 세그먼트 트리를 사용하는데, 이전처럼 구간 합을 구하는게 아니라 구간 곱을 구하는 것이다.
• 구간 합을 구할 때는 아래처럼 update 문을 구현했는데, 이는 0 이 들어왔을 때 구간 곱을 커버하지 못하는 구조이다.

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

• 그래서 init 문처럼 tree[node]를 업데이트 하되, 구간 안에 있는 부분만 진핸한다.

코드

• 최종 코드는 아래와 같다.

#include <bits/stdc++.h>

using namespace std;

void solution(int N, int M, int K);
long long init(int start, int end, int node);
long long multiple(int start, int end, int node, int left, int right);
long long update(int start, int end, int node, int index, long long prev, long long curr);

const int MAXSIZE = 1000000;
const long long MOD = 1000000007;
long long tree[MAXSIZE * 4];
int arr[MAXSIZE];



int main()
{
	int N, M, K;
	cin >> N >> M >> K;
	for (int i = 0; i < N; i++)
	{
		cin >> arr[i];
	}

	
	solution(N, M, K);
}

void solution(int N, int M , int K)
{
	init(0, N - 1, 1);

	for (int i = 0; i < M + K; i++)
	{
		int cmd;
		cin >> cmd;
		if (cmd == 1)
		{
			int from;
			long long to;
			cin >> from >> to;

			update(0, N - 1, 1,from -1, arr[from-1], to);
			arr[from -1] = to;

		}
		if (cmd == 2)
		{
			int from, to;
			cin >> from >> to;
			long long s = multiple(0, N - 1, 1, from-1, to-1);
			cout << s << "\n";
		}
	}
}

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

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

long long update(int start, int end, int node, int index, long long prev, long long curr)
{
	// 구간 사이에 인덱스가 없다면, 갱신 없이 tree[node]를 반환한다.
	if (index < start || end < index) return tree[node];
	if (start == end) return tree[node] = curr;
	int mid = (start + end) / 2;
	return tree[node] = (update(start, mid, 2 * node, index, prev, curr) % MOD) * (update(mid + 1, end, 2 * node + 1, index, prev, curr) % MOD) % MOD;
}