백준 11505번 [구간 곱 구하기](C++)-yes6686- 티스토리

백준 문제 풀이: 11505 [구간 곱 구하기]

---

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

문제 설명:

주어진 수열에서 다음 두 가지 작업을 처리하는 프로그램을 작성합니다:

• 1 x y: 수열의 x번째 원소를 y로 변경합니다.
• 2 x y: 수열의 x번째 원소부터 y번째 원소까지의 곱을 구한 후, 1,000,000,007로 나눈 나머지를 출력합니다.

---

문제 해결 코드

#include <iostream>
#include <algorithm>
using namespace std;

long long int arr[1000001];
long long int seg[4000001];

long long int go(int n, int s, int e) {
    if (s == e) {
        return seg[n] = arr[s];
    } else {
        int mid = (s + e) / 2;
        long long int left = go(2 * n, s, mid);
        long long int right = go(2 * n + 1, mid + 1, e);
        seg[n] = (left * right) % 1000000007;
        return seg[n];
    }
}

long long int mul(int n, int s, int e, int l, int r) {
    if (e < l || r < s) return 1;
    if (l <= s && r >= e) {
        return seg[n];
    }
    int mid = (s + e) / 2;
    long long int left = mul(n * 2, s, mid, l, r);
    long long int right = mul(n * 2 + 1, mid + 1, e, l, r);
    return (left * right) % 1000000007;
}

int change(int n, int s, int e, int i, long long int d) {
    if (i < s || i > e) return seg[n];
    if (s == e) {
        seg[n] = d;
        return seg[n] % 1000000007;
    }
    if (s != e) {
        int mid = (s + e) / 2;
        long long int left = change(n * 2, s, mid, i, d);
        long long int right = change(n * 2 + 1, mid + 1, e, i, d);
        return seg[n] = (left * right) % 1000000007;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m, k;
    cin >> n >> m >> k;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    go(1, 0, n - 1);
    long long int a, b, c;
    for (int i = 0; i < m + k; i++) {
        cin >> a >> b >> c;
        if (a == 1) {
            arr[b - 1] = c;
            change(1, 0, n - 1, b - 1, c);
        } else if (a == 2) {
            cout << mul(1, 0, n - 1, b - 1, c - 1) % 1000000007 << '\n';
        }
    }
}

---

코드 설명

• 세그먼트 트리 초기화: 수열의 곱을 계산할 수 있도록 각 구간의 곱을 세그먼트 트리에 저장합니다.
• 구간 곱 계산: 특정 구간의 곱을 계산하여 1,000,000,007로 나눈 나머지를 반환합니다.
• 값 변경 처리: 세그먼트 트리를 갱신하여 변경된 값을 반영합니다.

시간 복잡도

세그먼트 트리의 초기화와 쿼리 처리는 O(log n)입니다. 따라서 전체 시간 복잡도는 O((n + (m + k) log n))입니다.

---

결과

이 코드는 세그먼트 트리를 사용하여 구간 곱 문제를 효율적으로 해결했습니다. 추가적인 질문이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!