[C++] 11505번 구간 곱 구하기 - 자료 구조, 세그먼트 트리

11505번 구간 곱 구하기

1. 문제

• N개의 수가 있다. 이 때 다음 쿼리를 수행하라.
  • 1 b c : b번째 수를 c로 바꾸기
  • 2 b c : b부터 c까지의 곱을 구하여 출력하기

<입력>

• - 1 -   : 수의 개수 \(N(1 \leq N \leq 1,000,000)\), 수의 변경이 일어나는 횟수 \(M(1 \leq M \leq 10,000)\), 구간의 곱을 구하는 횟수 \(K(1 \leq K \leq 10,000)\)
• - N개의 줄 -   : N개의 숫자
• - M+K개의 줄 -   : a, b, c;

<출력>

• K줄에 걸쳐 구한 구간의 곱을 1,000,000,007로 나눈 나머지를 출력한다.

2. 재정의

• 유동적인 연속적인 수열의 곱을 계산하라

3. 해결 방법

• 세그먼트 트리 기본 문제

4. 실수한 점, 개선할 점

• no와 start, end를 혼선하지 말기
• 첫 번째 숫자는 A[0]이 아닌 A[1]에 넣기

 

<코드>

#include <iostream>

using namespace std;
typedef long long ll;

const ll mod = 1000000007;
const int MAX_N = 1000001;
const int MAX_TR = MAX_N*4;

// <문제>
// 수의 개수 N, 수의 변경이 일어나는 횟수 M, 구간의 곱을 구하는 횟수 K
int N, M, K;
// 수열 A[]
int A[MAX_N];

// <세그먼트 트리>
// 트리
ll tr[MAX_TR];

ll init(int no, int start, int end) {
    if(start == end)
        return tr[no] = A[start];
    int mid = (start + end)/2;
    return tr[no] = init(no*2, start, mid) * init(no*2+1, mid+1, end) % mod;
}

void update(int start, int end, int no, int idx, int diff) {
    if(idx < start || end < idx)
        return;
    if(start == end) {
        tr[no] = diff;
        return;
    }
    int mid = (start + end)/2;
    update(start, mid, no*2, idx, diff);
    update(mid+1, end, no*2+1, idx, diff);
    tr[no] = tr[no*2] * tr[no*2+1] % mod;
}

ll query(int start, int end, int no, int left, int right) {
    if(right < start || end < left)
        return 1;
    if(left <= start && end <= right)
        return tr[no];
    int mid = (start + end)/2;
    return query(start, mid, no*2, left, right) * query(mid+1, end, no*2+1, left, right) % mod;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    cin >> N >> M >> K;
    for(int i=1; i<=N; i++)
        cin >> A[i];
        
    // 세그먼트 트리 초기화
    init(1, 1, N);
    
    for(int i=0; i<M+K; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        if(a % 2)
            update(1, N, 1, b, c);
        else
            cout << query(1, N, 1, b, c) << '\n';
    }
    
    return 0;
}

 

<문제 바로가기>

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

11505번: 구간 곱 구하기

 

※현재 고등학교 등교 중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고 있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.