🚀 What I Will Learn

• 세그먼트 트리(Segment Tree)에 대해 이해하기
• 세그먼트 트리를 활용하여 구간 합을 구하는 방법 학습하기

구간트리(Segment Tree)란? 구간트리는 특정 구간에서 특정한 값을 뽑아올 때 유용하게 사용. 세그먼트 트리라고도 한다.

---

세그먼트 트리 (구간 트리, Segment Tree)

1️⃣ 구간 합이란?

• 구간 합은 여러 개의 데이터가 연속적으로 존재할 때
• 특정한 범위의 데이터의 합을 구하는 것을 의미

✔️ 선형적으로 구간 합 구하기

• 하나씩 검사를 하겠다?!

1) 배열 초기화

2) 구간 합 구하기

• 예시) 인덱스 2부터 10까지 접근해서 하나씩 더한다
  • 합계: 45

선형적으로 구간 합을 구하는 과정은 𝑂(𝑁)의 시간 복잡도를 가진다

---

2️⃣ 세그먼트 트리

✔️ 트리 구조로 구간 합 구하기

• 선형적으로 구간 합을 구하는 것은 비효율적이다
• 트리 구조를 활용하여 구간 합을 구하는 과정은 𝑂(𝑙𝑜𝑔𝑁)의 시간 복잡도를 가진다

1) 완전 이진 트리에 데이터 삽입

2) 구간 합 트리 생성

• 특정 범위 인덱스의 값을 저장
  • 첫 번째 루트는 인덱스 1부터 시작. 루트는 전체 데이터인 0~6까지 인덱스의 모든 데이터의 합
  • 루트의 왼쪽 자식은 인덱스 0~3까지의 데이터 합
  • 루트의 오른쪽 자식은 인덱스 4~6까지의 데이터 합

재귀적으로 호출하면서 현재 가지고 있는 구간에 대한 정보를 반으로 나누고, 이 정보를 왼쪽과 오른쪽 자식으로 전달해서 값을 구한다

3) 완성

---

✨ tl;dr

• 세그먼트 트리에서의 구간 합 계산 및 원소 수정 과정은 𝑂(𝑙𝑜𝑔𝑁)의 시간 복잡도를 가진다

시간복잡도: 문제를 해결하는데 걸리는 시간과 입력의 함수 관계.
컴퓨터과학에서 알고리즘의 시간복잡도는 입력을 나타내는 문자열 길이의 함수로서 작동하는 알고리즘을 취해 시간을 정량화하는 것을 의미