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

접근

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

11505번: 구간 곱 구하기

세그먼트 트리를 이용하여 답을 구할 수 있다. 세그먼트 트리란 구간 합을 빠르게 구할 때 자주 사용하는 알고리즘으로써 예를 들어 10개의 요소가 있다면 1번 노드에 1~10 까지의 합을 계산해두고, 그 자식 노드인 2, 3번 노드에 각각 0~5, 6~10 까지의 합을 계산해둔다. 이를 반복하여 트리의 맨 아래까지 모두 계산해두면, 구간의 합을 구할 때 시간을 매우 단축시킬 수 있다.

처음에 주어진 숫자들을 가지고 세그먼트 트리를 구성하는 Init 함수, 주어진 구간에서의 곱을 구하는 Multiply 함수, index 번째 수를 new_num으로 바꾸는 Update 함수 세가지로 구성된다.

코드

#include <algorithm>
#include <iostream>

using namespace std;

#define endl '\n'
#define MAX_N 1000002
#define MOD 1000000007

int N, M, K;
int NUM[MAX_N];
long long int SegmentTree[MAX_N * 4];

// NUM 배열에 저장된 정보를 가지고 세그먼트 트리를 초기화하는 함수
long long int Init(int start, int end, int node) {
    if (start == end) return SegmentTree[node] = NUM[start];
    int mid = (start + end) / 2;
    return (SegmentTree[node] = (Init(start, mid, node * 2) * Init(mid + 1, end, node * 2 + 1)) % MOD);
}

// left~right 까지 구간의 곱을 구하는 함수
long long int Multiply(int start, int end, int node, int left, int right) {
    if (end < left || right < start) return 1;
    if (left <= start && end <= right) return SegmentTree[node];
    int mid = (start + end) / 2;
    return ((Multiply(start, mid, node * 2, left, right) * Multiply(mid + 1, end, node * 2 + 1, left, right)) % MOD);
}

// index 번째 수를 new_num으로 바꾸는 함수
long long int Update(int start, int end, int node, int index, int new_num) {
    if (index < start || end < index) return SegmentTree[node];
    if (start == end) return SegmentTree[node] = new_num;
    int mid = (start + end) / 2;
    return SegmentTree[node] = (Update(start, mid, node * 2, index, new_num) * Update(mid + 1, end, node * 2 + 1, index, new_num)) % MOD;
}

int main(int argc, char** argv) {
    // freopen 주석 처리
    freopen("input.txt", "r", stdin);

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> N >> M >> K;
    for (int i = 1; i <= N; i++) {
        cin >> NUM[i];
    }
    Init(1, N, 1);
    int a, b, c;
    for (int i = 0; i < M + K; i++) {
        cin >> a >> b >> c;
        if (a == 1) {
            Update(1, N, 1, b, c);
        } else {
            cout << Multiply(1, N, 1, min(b, c), max(b, c)) << endl;
        }
    }

    return 0;
}

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!