solved.ac CLASS 6 구간 트리 문제 정리

solved.ac

서론

이 글에서 제시된 문제 중 Fenwick Tree로 풀이할 수 있는 문제들은 Segment Tree로 풀이할 수도 있습니다.

일부 스포일러가 존재합니다.

 

1. BOJ 2042번 - 구간 합 구하기

Fenwick Tree 기초

 

2. BOJ 2357번 - 최솟값과 최댓값

Segment Tree 기초

 

3. BOJ 11505번 - 구간 곱 구하기

Segment Tree 기초

수의 범위에 0이 포함되어서 Fenwick Tree 풀이는 어려워보인다.

 

4. BOJ 14428번 - 수열과 쿼리 16

Segment Tree

 

5. BOJ 2243번 - 사탕상자

Fenwick Tree select 연산

 

6. BOJ 7578번 - 공장

Fenwick Tree

 

7. BOJ 3653번 - 영화 수집 (Movie collection)

Fenwick Tree

 

8. BOJ 6549번 - 히스토그램에서 가장 큰 직사각형 (Largest Rectangle in a Histogram)

stack 풀이와 Segment Tree + 분할 정복 풀이가 존재한다.

두 풀이 모두 시도해보기를 바란다.

자세한 풀이는 링크에서 확인할 수 있다.

 

끝

끝