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

문제

 

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

11505번: 구간 곱 구하기

 

 

풀이

 

solved.ac 난이도: Gold 1

 

 

세그먼트 트리(구간 트리)를 이용해야 제한시간 안에 풀 수 있는 문제. 

세그먼트 트리를 모른다면 간단한 풀이로는 이해하기 힘드므로 백준님의 깔끔한 설명을 보고 오자.

세그먼트 트리 (Segment Tree) - Baekjoon Online Judge

 

세그먼트 트리는 이름처럼 노드마다 자신이 포함하는 구간의 정보를 저장해둔다.

구간은 두 개의 하위 노드로 내려가면서 반으로 나누어지고, 나뉜 각 노드들도 해당 구간의 정보를 저장한다.

각 구간을 가리키는 node로의 접근은 힙 자료구조처럼 root 노드를 1이라고 할 때 각 node 자식 노드들은 

왼쪽 노드는 node*2, 오른쪽 노드는 node*2+1로 접근 가능하다.

 

이번 문제에서는 각 구간의 곱을 구하는 문제이므로 트리의 노드에는 해당 노드가 포함하는 구간의 곱을 저장해 두자.

 

해당 문제를 풀기 위한 세그먼트 트리는 크게 3가지 함수로 구현할 수 있다.

 

1. 초기화 함수 

 

ll Init(int left, int right , int node){
  if(left == right)
    return segment_tree[node] = arr[left];
  
  int mid = (left+right)/2;
  segment_tree[node] = ( Init(left,mid, node*2) * Init( mid+1, right, node*2 +1))%MOD;
  return segment_tree[node];
}

 

 

2. 업데이트 함수

 

ll Update(int left, int right , int node, int idx, ll num){
  if(right < idx || idx < left )
    return segment_tree[node];  //변화 x의 값을 반환
  
  if(left == right){  //== idx인 경우
    return segment_tree[node] = num;
  }
 
  int mid = (left+right)/2;
  segment_tree[node] = (Update(left,mid, node*2,idx ,num ) * Update(mid+1, right, node*2 +1,idx ,num ))%MOD;
  return segment_tree[node];
}

 

 

3. 질의 함수

 

ll Query(int left, int right, int query_left ,int query_right , int node){ 
  if( right < query_left || query_right < left)
    return 1;
  
  if(query_left <= left  && right <= query_right )
    return segment_tree[node];
  //else
 
  int mid = (left+right)/2;
  return (Query(left, mid, query_left, query_right ,node*2) *Query(mid+1, right, query_left, query_right ,node*2+1) )%MOD ;
}

 

특히 중요한 질의 함수를 살펴보자.

 

현재의 node가 포함하는 구간이 [left, right]와 

곱을 구하려는 구간 [query_left, query_right]에는 4가지 포함관계가 존재한다.

 

1. [query_left, query_right]와 [left, right]가 겹치지 않는 경우

 이 경우는 구해야 하는 범위[query_left, query_right]가 해당 노드의 포함 구간과 전혀 다르므로 1을 반환하여 곱의 결과에 영향을 주지 않도록 한다.

 

1.case

 

2. [query_left, query_right]가 [left, right]를 포함하는 경우 (query_left <= left && right <= query_right)

[query_left, query_right] 안에 해당 노드의 범위[left, right]가 포함되어 있기 때문에

해당 구간은 모두 구간 곱에 사용되어야 한다. 따라서 해당 노드에 미리 구해놓은 [left, right]의 구간 곱을 반환해주자.

 

2.case

 

 

3. [left, right]가 [query_left, query_right]를 포함하는 경우 (left < query_left  && query_right  < right)

노드의 구간이 구하려는 범위[query_left, query_right]  보다 크기 때문에 구하려는 구간 곱 이외의 값들이 해당 노드에는 이미 곱해져 저장되어 있다. 

따라서  노드의 범위 [left, right]가 구하려는 범위[query_left, query_right] 안에 포함될 수 있도록 하위 노드를 탐색해야 한다.

 

3.case

 

4.  [query_left, query_right]와 [left, right]가 겹쳐지는 부분이 있는 경우

이 경우도 노드의 범위[left, right]가 [query_left, query_right]  안에 포함될 수 있도록 왼쪽 노드와 오른쪽 노드를 재귀 호출하여 하위 노드를 탐색해야 한다.

 

 

4.case

 

 

 

코드