[백준/C++][구간 곱 구하기(11505번)-세그먼트 트리]

문제

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

11505번: 구간 곱 구하기

문제 풀이

이 문제는 세그먼트 트리를 이용해서 푸는 문제이다. 기본적으로 세그먼트 트리의 지식이 있어야 풀 수 있다.

세그먼트 트리에서 구간 합을 구하는 방법과 비슷하게 풀었다.

1. 초기화를 해줄 때 자식 노드들의 곱으로 노드를 초기화했다.

2. 업데이트를 해줄 때는 구간에 있는 노드들을 전부 바꿨다. (리프 노드도 바꾸어줌)-> 리프 노드부터 자식 노드들의 곱으로 바꿨다는 의미.

3. 구간 곱을 구할 때에는 구간이 아니라면 1을 반환(0을 반환하면 곱이므로 구간 곱이 0이 됨) 구간에 들어오면 해당 노드 반환, 겹치면 두 자식의 곱을 반환.

 

코드

#include <iostream>
#include <vector>
#include <cmath>
#include <cstdio>
#define MOD 1000000007
using namespace std;
vector<int> v;
vector<long long> tree;
long long init(int node,int start,int end){
    if(start == end){
        return tree[node] = v[start];
    }
    else{
    return tree[node] = init(node*2,start,(start+end)/2)*init(node*2+1,(start+end)/2+1,end)%1000000007;
    }
}
long long update(int node,int start,int end,int idx,int num){
    if(idx>end || idx<start){return tree[node];}
    if(start == end){return tree[node] = num;}
    return tree[node] = update(node*2,start,(start+end)/2,idx,num)*update(node*2+1,(start+end)/2+1,end,idx,num)%1000000007;
}
long long sum(int node,int start,int end,int left,int right){
    if(left>end || right<start){return 1;}
    if(left<=start && right>=end){
        return tree[node];
    }
    else{
    return sum(node*2,start,(start+end)/2,left,right)*sum(node*2+1,(start+end)/2+1,end,left,right)%1000000007;
    }
}
int main(void){
    int N,M,K;
    scanf("%d%d%d",&N,&M,&K);
    v.resize(N);
    int h = (int)ceil(log2(N));
    int vector_size = (1<<(h+1));
    tree.resize(vector_size);
    for(int i = 0;i<N;i++){
        scanf("%d",&v[i]);
    }
    init(1,0,N-1);
    for(int i =0;i<M+K;i++){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        if(a == 1){
            update(1,0,N-1,b-1,c);
        }
        else if(a == 2){
            cout << sum(1,0,N-1,b-1,c-1)<<"\n";
        }
    }
}