세그먼트 트리 2

[백준 2357] 최솟값과 최댓값 - 세그먼트 트리

https://www.acmicpc.net/problem/2357 2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100 www.acmicpc.net 문제 N(1 ≤ N ≤ 100,000) 개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000) 개 주어졌을 때는 어려운 문제가 된다. 이 문제를 해결해 보자. 여기서 a번째라는 것은 입력되는 순서로 a번째라는 이야..

세그먼트 트리(Segment Tree) 자료구조

세그먼트 트리(Segment Tree) 자료구조는 누적 합 알고리즘의 심화 버전으로 이해될 수 있다. 크기가 N인 배열이 주어졌을 때, 누적 합 알고리즘의 시간복잡도는 O(N)이다. 이도 빠르긴 하지만, N의 크기가 더 커졌을 경우에는 이 또한 시간 초과가 나올 수 있다. 세그먼트 트리라는 완전 이진 트리 형태의 자료구조를 사용하면 배열의 특정 구간의 합을 구하는 시간복잡도는 O(logN)으로 훨씬 더 시간을 단축할 수 있다. 배열의 크기가 N일 경우의 세그먼트 트리의 형태은 다음과 같다. 하나의 노드마다 인덱스 i~인덱스 j 사이인 배열 구간의 누적 합 결과값이 들어간다. 세그먼트 트리 만들기 완전 이진 트리는 배열을 통해 구현한다. 어떠한 부모 노드의 두 자식 노드들은 부모 노드의 인덱스를 idx라고..

자료구조 2023.02.04
728x90