백준 11505 - 구간 곱 곱하기(C++)

문제 링크입니다. https://www.acmicpc.net/problem/11505

 

세그먼트 트리를 이용한 문제입니다.

 

세그먼트 트리를 통해 원하는 구간의 곱을 구하는 문제입니다.

 

 

먼저, 주어진 값을 통해서 세그먼트 트리를 만드는 과정이 필요합니다.

 

세그먼트 트리를 만들었다면, 주어진 a의 값을 통해서 트리를 변경하거나, 구간의 곱을 구하는 코드를 만들어야합니다.

 

1. 주어진 값으로 트리 변경하기

-> 원하는 위치에 원하는 값으로 트리를 변경해야합니다.

    1-1. 원하는 위치와 현재 탐색하는 범위가 맞는지를 확인해야 합니다.

    -> 위치가 다르다면, 값을 바꾸지 않고 현재 값을 그대로 return 해줍니다.

    1-2. 탐색할 범위가 하나라면(시작범위와 끝 범위가 같다면) 해당 위치가 바꾸길 원하는 위치이기에 트리를 바꿔줍니다.

    1-3. 범위는 맞지만, 범위가 2개 이상이라면

    ->좌측과 우측 트리를 확인해 해당 트리의 곱으로 바꿔줍니다.

 

2. 구간의 곱을 구하는 트리

 -> 주어진 구간의 곱을 찾아서 출력해줘야 합니다.

    2-1. 곱하려는 구간과 현재 탐색 중인 구간이 맞지 않다면 '1'을 return 해줍니다.

    2-2. 곱하려는 구간에 탐색 중인 구간이 포함된다면 해당 트리의 값을 return 해줍니다.

    2-3. 위의 2개의 경우가 아니라면

    -> 좌측과 우측 트리를 확인해 곱을 return 해줍니다.

    -> 2-3번이 실행된다면, 2-2에서 return된 값들을 통해 마지막에 곱해져서 return 됩니다.

 

 

자세한 것은 코드를 참고해주세요.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
#include <string>
#include <cmath>
#define INF 987654321
#define Mod 1000000007

using namespace std;

int N, M, K;
long long Index[1000001];
vector<long long> Tree;

long long segment_tree(int node, int st, int fin) {
	if (st == fin) return Tree[node] = Index[st];
	int mid = (st + fin) / 2;
	long long left_sum = segment_tree(node * 2, st, mid);
	long long right_sum = segment_tree(node * 2 + 1, mid + 1, fin);
	return Tree[node] = (left_sum * right_sum) % Mod;
}

long long update_tree(int st, int fin, int loc, long long update, int node) {
	if (loc < st || loc > fin) return Tree[node];
	if (st == fin) return Tree[node] = update;
	int mid = (st + fin) / 2;
	return Tree[node] = (update_tree(st, mid, loc, update, node * 2) * update_tree(mid + 1, fin, loc, update, node * 2 + 1) % Mod);
}

long long get_sum(int st, int fin, int left, int right, int node) {
	if (right < st || left > fin) return 1;
	if (left <= st && right >= fin) return Tree[node];
	int mid = (st + fin) / 2;
	return (get_sum(st, mid, left, right, node * 2) * get_sum(mid + 1, fin, left, right, node * 2 + 1) % Mod);
}

void solve() {
	int height = ceil(log2(N));
	Tree.resize(1 << (height + 1));
	segment_tree(1, 0, N - 1);
	for (int i = 1; i <= M + K; i++) {
		long long  a, b, c;
		scanf("%lld %lld %lld", &a, &b, &c);
		if (a == 1) {
			update_tree(1, N, b, c, 1);
			Index[b] = c;
		}
		else {
			cout << get_sum(1, N, b, c, 1) << "\n";
		}
	}
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M >> K;
	for (int i = 0; i < N; i++) {
		scanf("%lld", &Index[i]);
	}
	solve();
	
	return 0;
}

 

 

 

질문 및 조언은 댓글을 남겨주세요.