BOJ 11505 | 구간 곱 구하기

리프 노드부터 업데이트하는 세그트리를 만들 줄 아십니까? 라고 물어보는 문제다.

구간 합 구하기에서 update() 함수를 Top-down으로 만들었다면 이 문제에서는 0의 특수성 때문에 리프 노드부터 작동하도록 해야 한다.

두 방법 모두 구현해보면 세그트리의 숙련도가 조금 올라갈 것 같다.

오늘부터 세그트리 공부를 시작했기 때문에 지금 풀기에 굉장히 좋은 문제라고 생각한다.

원소가 5개인 세그트리의 그림이다.

세그트리를 생성하기 위해서 필요한 $SIZE$는 $2^{Ceil(lgN)+1}$이다.
계산해서 생성해도 괜찮지만 편하게 $4N$으로 생성하자.

세그트리를 생성하는 init() 함수는 다음과 같이 작동한다.

init(s, e) = init(s, mid) * init(mid+1, e)

여기서 mid는 (s+e)/2로 계산할 수 있다. int형으로 계산하므로 모든 연산은 내림이 기본 전제로 깔려 있음에 주의하자.

어떤 값을 업데이트하라는 쿼리가 들어오면 그 값 하나만 들어있는 리프 노드까지 내려가면서 update()를 수행한다.

업데이트가 필요하다면 업데이트 이후 return 하고, 업데이트가 필요하지 않은 노드라면 업데이트 없이 return 한다.

tree[i] = update(left) + update(right)
return tree[i]

구조로 업데이트 할 수 있다. 구간 곱 구하기는 0으로 한번 업데이트 된 이후에는 되돌리기 어렵기 때문에 이렇게 만들어야 한다.

마지막으로 구간 곱을 구해주는 query() 함수가 필요하다.

query(s, e) = query(s, mid) * query(mid+1, e)

init과 같이 진행된다. 쿼리당 복잡도 $O(logN)$에 처리할 수 있다.
간단한 세그트리가 사용되는 문제들은 여기서 구성한 세그 클래스로 충분히 날먹이 가능하니 잘 이용해보자.

코드

#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
constexpr bool local = true;
#else
constexpr bool local = false;
#endif

#define FASTIO ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define ll long long

#define debug if constexpr (local) std::cout
#define endl '\n'

#define MOD 1000000007

class Segtree{
private:
	vector<ll> tree;
	
public:
	Segtree(int treeSize){
		tree.resize(4 * treeSize);
	}
	
	ll init(vector<ll> &nums, int node_idx, int s, int e){
		//debug << "INIT s " << s  << " e " << e << " idx " << node_idx << endl;
		if (s == e){ //leaf node
			//debug << "tree[" << node_idx << "] = " << nums[s] << endl;
			return tree[node_idx] = nums[s];
		}
		
		ll lnode = init(nums, node_idx*2, s, (s+e)/2);
		ll rnode = init(nums, node_idx*2+1, (s+e)/2+1, e);
		tree[node_idx] = (lnode * rnode) % MOD;
		//debug << "NODE " << node_idx << " UPDATE " << tree[node_idx] << endl; 
		return tree[node_idx];
	}
	
	ll update(int node_idx, int s, int e, int idx, ll value){
		if (idx < s || idx > e) return tree[node_idx];
		if (s == e) return tree[node_idx] = value;
		
		ll lnode = update(node_idx*2, s, (s+e)/2, idx, value);
		ll rnode = update(node_idx*2+1, (s+e)/2+1, e, idx, value);
		
		debug << "NODE " << node_idx << " UPDATE " << (lnode*rnode) % MOD << endl; 
		return tree[node_idx] = (lnode*rnode) % MOD;
		
	}
	
	ll query(int node_idx, int s, int e, int l, int r){
		if (l > e || r < s) return 1;
		
		if (l <= s && e <= r) return tree[node_idx];
		
		ll lnode = query(node_idx*2, s, (s+e)/2, l, r);
		ll rnode = query(node_idx*2+1, (s+e)/2+1, e, l, r);
		
		return (lnode * rnode) % MOD;
	}
	
	
	
};

int main(){
	FASTIO;
	ll N, M, K; cin >> N >> M >> K;
	Segtree SG = N;
	
	vector<ll> nums;
	nums.push_back(1);
	for (int i = 0; i < N; i++){
		ll t; cin >> t;
		nums.push_back(t);
	}
	
	SG.init(nums, 1, 1, nums.size()-1);
	
	for (int i = 0; i < M+K; i++){
		ll o, x, y; cin >> o >> x >> y;
		if (o == 1){
			SG.update(1, 1, nums.size()-1, x, y);
		}
		else{
			cout << SG.query(1, 1, nums.size()-1, x, y) % MOD << endl;
		}
	}
}