11505 구간 곱 구하기

BOJ::11505 구간 곱 구하기

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

세그먼트 트리를 활용하는 문제이다.

2042 구간합 구하기는 업데이트시 어려운점이 없었는데,

이 문제는 업데이트시 0으로 바뀌는 경우 상위값들이 모두 0으로 바뀌는 부분 때문에 해결하느라 굉장히 힘들었다.

다른사람들 코드 보면서 엄청 간단하고 직관적으로 짜시는 분들이 있는데,

나도 그렇게 짤 수 있도록 반복적인 연습이 필요할 것 같다.

#include <stdio.h>
#include <vector>
#include <math.h>
#define MOD 1000000007
using namespace std;
typedef long long ll;
 
ll init(vector<ll> &a, vector<ll> &tree, int node, int start, int end) {
    // 리프노드인 경우
    if (start == end) {
        return tree[node] = a[start];
    }
    // 리프노드가 아닌 경우
    // 자식노드의 곱을 값으로 갖는다.
    return tree[node] = 
        (init(a, tree, node * 2, start, (start + end) / 2) *
        init(a, tree, node * 2 + 1, (start + end) / 2 + 1, end))%MOD;
}
 
ll update(vector<ll> &tree, int node, int start, int end, int idx, ll val) {
    // start와 end 사이의 idx가 아니면 현재값 그대로 반환
    if (start > idx || idx > end) return tree[node];
    // 트리에서 a[idx-1]과 같은 값을 가지는 노드 val로 업데이트
    if (start == end) return tree[node] = val;
    
    // 트리에서 a[idx-1]과 같은 값은 가지는 노드의 부모노드를 타고 올라가며 업데이트
    return tree[node] = (update(tree, node * 2, start, (start + end) / 2, idx, val)
        * update(tree, node * 2 + 1, (start + end) / 2 + 1, end, idx, val)) % MOD;
}
 
ll multi(vector<ll> &tree, int node, int start, int end, int left, int right) {
    // 현재 구하려는 범위가 아닌경우
    if (left > end || right < start) return 1;
    // left와 right가 포함되는경우 포함하는 범위만큼의 값 반환
    if (left <= start && end <= right) {
        return tree[node];
    }
    //포함되는 범위 값들의 곱 반환
    return 
        (multi(tree, node * 2, start, (start + end) / 2, left, right) *
        multi(tree, node * 2 + 1, (start + end) / 2 + 1, end, left, right))%MOD;
}
 
int main() {
    int n, m, k;
    scanf("%d %d %d", &n, &m, &k);
    m += k;
    // 입력받을 a벡터
    vector<ll> a(n);
    for (int i = 0; i < n; i++) scanf("%lld", &a[i]);
    int h = (int)ceil(log2(n));
    // 트리를 생성할 tree 벡터
    vector<ll> tree(1 << h + 1);
 
    init(a, tree, 1, 0, n - 1);
 
    while (m--) {
        ll x, y, z;
        scanf("%lld %lld %lld", &x, &y, &z);
        if (x == 1) {
            update(tree, 1, 0, n - 1, y - 1, z);
        }
        else {
            printf("%lld \n", multi(tree, 1, 0, n - 1, y - 1, z - 1));
        }
    }
}