[백준 11505번] [세그먼트 트리] 구간 곱 구하기

Approach

구간 합 문제랑 비슷하면서도 조금 다르다.

구간 합을 구하는 경우는 update하는 과정에서 하위 노드들의 값을 재참조할 필요가 없이, parameter로 주입한 value값을 토대로 갱신만 해주면 된다. 구간 곱의 경우는 0의 존재때문에 다시 갱신해주는 것이 편하다.

 

잘 생각해보면 update를 할 때, 변한 index를 포함하지 않는 부분은 기존 seg값을 재활용하고 포함하는 경우만 갱신해주면 된다.

Code

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

using namespace std;
typedef long long ll;
ll seg[4000000];

ll update(int node_index, int node_left, int node_right, int index, int value){
    if(index < node_left || node_right < index) return seg[node_index]; // Out of bound
    if(node_left == node_right){
        return seg[node_index] = (value % 1000000007);
    }
    else{
        int mid = (node_left + node_right) / 2;
        return seg[node_index] = (update(node_index * 2, node_left, mid, index, value) *
        update(node_index * 2 + 1, mid + 1, node_right, index, value)) % 1000000007;
    }
}

ll query(int node_index, int node_left, int node_right, int query_left, int query_right){
    if(query_right < node_left || node_right < query_left) return 1;
    else if(query_left <= node_left && node_right <= query_right) return seg[node_index];

    int mid = (node_left + node_right) / 2;
    return (query(node_index * 2, node_left, mid, query_left, query_right) *
           query(node_index * 2 + 1, mid + 1, node_right, query_left, query_right)) % 1000000007;
}

int main(void){
    fastio;
    fill_n(seg, 4000000, 1);
    ll N, M, K;
    cin >> N >> M >> K;

    for(int i = 1; i <= N; i++){
        ll t;
        cin >> t;
        update(1, 1, N, i, t); 
    }

    for(int i = 0; i < M + K; i++){
        ll t, b, c;
        cin >> t >> b >> c;
        if(t == 1){
            update(1, 1, N, b, c);
        }
        else{
            cout << query(1, 1, N, b, c) << "\n";
        }
    }
    return 0;
}