반응형
Segment tree
-
BOJ) 구간 합 구하기 (2042 번)알고리즘/백준 2021. 1. 5. 18:09
구간 합 구하기 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 세그먼트 트리를 이용해서 푸는 문제다. 우선, 이 문제를 풀기 위해서 세그먼트 트리에 대해서 공부해야했다. 백준 사이트에 블로그란에 기재되어있는 세그먼트 트리를 보고 풀었다. 세그먼트 트리란 무엇인가?? 먼저, 세그먼트 트리는 배열의 크기가 커질 경우, 연산 식에 유용하다. 공간 복잡도가 O(N^2)이고 시간 복잡도가 O(N^2)인 배열에 대한 연산이 있다면, 세그먼트 트리를 이용하여 O..