구간 곱 구하기

백준 11505번: 구간 곱 구하기

아이디어

구간 합 구하기랑 비슷한데 좀 생각할게 많다.
구간 곱을 구하는 함수는 범위를 벗어났을 때 1을 반환한다.
Update가 살짝 느낌이 다르다. 루트부터 호출하여 리프 노드까지 내려가서 원하는 값으로 바꾸고, 하나씩 올라갈 때마다 자기 자식 두명 곱한 값으로 업데이트해준다. start == end일 때 함수를 바로 종료해야한다.

코드

#include <bits/stdc++.h>

using namespace std;

const int MOD = 1000000007;
int N, M, K;
vector<long long> arr; // 0부터 시작
vector<long long> tree; // 1부터 시작

long long init(int node, int start, int end) {
    if (start == end) {
        return tree[node] = arr[start];
    }
    else {
        return tree[node] = init(node*2, start, (start+end)/2)%MOD * init(node*2+1, (start+end)/2+1, end)%MOD;
    }
}

long long mul(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]%MOD;
    return mul(node*2, start, (start+end)/2, left, right)%MOD * mul(node*2+1, (start+end)/2+1, end, left, right)%MOD;
}

void update(int node, int start, int end, int idx, long long value) {
    if (idx < start || idx > end) return;
    if (start == end) {
        tree[node] = value;
        return;
    }
    update(node*2, start, (start+end)/2, idx, value);
    update(node*2+1, (start+end)/2+1, end, idx, value);
    tree[node] = tree[node*2]*tree[node*2+1]%MOD;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> M >> K;
    for (int i = 0; i < N; i++) {
        int x;
        cin >> x;
        arr.push_back(x);
    }

    int h = (int)ceil(log2(N));
    int tree_size = (1<<h+1);
    tree.resize(tree_size);
    init(1, 0, N-1);
    
    for (int i = 0; i < M+K; i++) {
        long long a, b, c;
        cin >> a >> b >> c;
        if (a == 1) {
            update(1, 0, N-1, b-1, c);
            arr[b-1] = c;
        }
        else if (a == 2) {
            cout << mul(1, 0, N-1, b-1, c-1)%MOD << '\n';
        }
    }
    return 0;
}

여담

node 범위 넘어가서 터지기 전에 호출을 멈춰야하는데 순서 살짝 잘못써서 한참 헤맸다.