[백준] 11505번 구간 곱 구하기

[적용한 알고리즘]

세그먼트 트리

 

[아이디어]

내용

 

[생각의 흐름 / 절차] 

내용

 

[교훈]

구간 합 구하기처럼 update 함수를 구성하면 안된다. 

앞으로 update 함수는 이렇게 써야지

 

<코드>

#include <cstdio>
#include <vector>
#include <cmath>
#define mod 1000000007
using namespace std;

long long construct(vector<long long> &a, vector<long long> &tree, int node, int start, int end){
    if (start == end){
        return tree[node] = a[start]; // 리프 노드인 경우 자기 자신을 등록 시켜야함.
    }
    else {
        int mid = (start + end) / 2; // 아니라면 자기 밑에 자식을 더해야 함.
        return tree[node] = ((construct(a, tree, node * 2, start, mid) % mod) * (construct(a, tree, node * 2 + 1, mid + 1, end) % mod)) % mod;
    }
}

long long update(vector<long long> &tree, int node, int start, int end, int index, long long newVal){
    if (index < start || index > end) return tree[node]; // 범위 밖에 있는 경우
    if (start == end) return tree[node] = newVal;
    if (start != end){ //리프 노드가 아닌 경우
        int mid = (start + end) / 2;
        return tree[node] = (update(tree, node * 2, start, mid, index, newVal) * update(tree, node * 2 + 1, mid + 1, end, index, newVal)) % mod;
    }
}
// 내가 구하고 싶은 값의 범위 : left ~ right, 현재 체크 하고 있는 노드의 범위 : start ~ end
long long mult(vector<long long> &tree, int node, int start, int end, int left, int right){
    if (left > end || right < start) { // 만약에 포함이 안되어있는 경우
        return 1;
    }
    if (left <= start && end <= right){
        return tree[node];
    }
    int mid = (start + end) / 2;
    return (mult(tree, node * 2, start, mid, left, right) * mult(tree, node * 2 + 1, mid + 1, end, left, right)) % mod;
}

int main(){
    int n, m, k;
    scanf("%d %d %d", &n, &m, &k);
    vector<long long> a(n);
    int tree_height = (int)ceil(log2(n));
    int tree_size = (1 << (tree_height + 1));
    vector<long long> tree(tree_size);

    for (int i = 0; i < n; i++){
        scanf("%lld", &a[i]);
    }
    construct(a, tree, 1, 0, n - 1);

    int t = m + k;
    while (t--){
        int oper;
        scanf("%d", &oper);

        if (oper == 1){
            int x;
            long long y;
            scanf("%d %lld", &x, &y);
            update(tree, 1, 0, n - 1, x - 1, y);
        }//update

        if (oper == 2){
            int left, right;
            scanf("%d %d", &left, &right);
            printf("%lld\n", mult(tree, 1, 0, n - 1, left - 1, right - 1));
        }//sum
    }

    return 0;
}