DAMPER's blog

이번 글은 세그먼트 트리 활용중 하나인 K번째 원소 찾기 입니다. https://www.acmicpc.net/problem/12899 12899번: 데이터 구조 첫째 줄에 사전에 있는 쿼리의 수 N 이 주어집니다. (1 ≤ N ≤ 2,000,000) 둘째 줄부터 N개의 줄에 걸쳐 각 쿼리를 나타내는 2개의 정수 T X가 주어집니다. T가 1이라면 S에 추가할 X가 주어지는 것입니 www.acmicpc.net 문제에는 두 가지 종류의 쿼리가 존재한다. 유형 1 : 데이터베이스 S에 자연수 X를 추가한다. 유형 2 : S에 포함된 숫자 중 X번째로 작은 수를 응답하고 그 수를 삭제한다. 쿼리는 최대 200만개 까지 가능하니 한 쿼리를 최대 O(NlogN)에 처리해야 한다. 다행히도(?) X의 범위는 1부터 ..

PS분야에서 정말 다양하게 쓰이고 있는 자료구조로 자유자재로 쓰고싶은 마음에 이번 기회에 정리하고자 한다. 세그먼트 트리는 흔히 일차원 배열의 특정 구간에 대한 쿼리를 빠르게 답하는 데 사용한다. 물론 다차원 배열의 특정 구간에 대한 세그먼트 트리도 구현이 가능하다. 가장 기본적인 예로 어떤 배열의 부분 구간의 최소치를 구하는 연산을 여러번 하는 것이다. 배열 A = {1, 2, 1, 4, 6, 1, 5, 8}가 있다면 구간[2, 4]의 최소값은 1이고 구간[6, 7]의 최소값은 5이다. 이 문제를 세그먼트 트리를 통해 O(qlogn)에 해결할 수 있다. 세그먼트 트리의 기본적인 아이디어는 주어진 배열의 구간들을 표현하는 이진 트리를 만드는 것이다. 루트는 전체 구간을 표현하고, 리프는 1개만을 표현한다..