고난이도 자료구조 세그먼트 트리 구현하면서 이해하기 2편(생성하고 합을 구하는 방법)

1. 세그먼트 트리의 표현 배열의 크기 N이 2의 거듭제곱꼴이면 Perfect binary tree이므로 트리의 높이 h는 각 높이의 노드의 수가 x개이면 $$h=log_{2} x$$ full binary tree라면 어떨까? 어떤식으로 구성되어 있느냐에 따라 조금 달라진다..... $h= \left \lceil log_{2} x \right \rceil$이기도 하고.. $H= \left \lceil log_{2} x \right \rceil +1$ 이기도 하고... 따라서 세그먼트 트리를 표현할 때, 배열을 이용해서 표현할 수 있고 세그먼트 트리 배열의 크기는 항상 그 크기가 일정한 높이 h인 perfect binary tree의 노드 수로 나타낼 수 있다 비어있는 부분은 0으로 채우든지 하면 되니..

• format_list_bulleted 세그먼트 트리
• · 2022. 12. 5.
• textsms

고난이도 자료구조 세그먼트 트리 개념 이해하기 1편

1. 특정한 구간에 존재하는 모든 수의 합 어떤 수열이 주어질때, 만약 특정 구간 [a,b]에 존재하는 모든 수의 합을 구하라고 한다면 어떻게 구할 수 있을까? 가장 쉬운 방법은, 그냥 반복문으로 [a,b]까지 돌아서 모든 수의 누적합을 구하면 된다 answer = 0 for i in range(a,b+1): answer += A[i] 만약 배열 A의 크기가 N일때, 최악의 경우 위 코드의 시간 복잡도는 O(N)이다. 1번부터 N번까지 다 더하라하면 O(N)이니까 여기까지는 괜찮은데 만약 이러한 질문을 M번이나 한다면? O(N)의 연산을 M번 수행해야하므로, 시간복잡도는 O(NM)이고 N,M이 매우 크다면, 당연히 매우 느리다 2. Prefix sum 만약 S[0] = 0이고, 1번부터 i번까지의 수열 ..

• format_list_bulleted 세그먼트 트리
• · 2022. 12. 5.
• textsms