1. 세그먼트 트리 주어진 데이터의 구간합과 데이터 업데이트를 빠르게 수행하기 위해 고안해낸 자료구조 2. 구간합 합배열(prefix sum)은 업데이트가 느림 arr[1]를 update 한다면 ? sum[1]부터 sum[9]까지 모든 값을 update 해야함 ➔ 느림 데이터의 업데이트가 빈번하게 일어나게 되면 합배열 성능 측면에서 안좋음 ➔ 속도유지를 위해 세그먼트 트리 사용 2. 원리 1) 트리 초기화 하기 ⓪ 샘플데이터 {5, 8, 4, 3, 7, 2, 1, 6} ① 리스트 길이 데이터의 개수(N) 이상이 되도록 트리 리스트를 만듬 2ᵏ≥ N을 만족하는 𝑘의 최솟값을 구한 후 2ᵏ * 2 N=8이므로 2³ ≥ 8 ➔ 2³ * 2 = 16 ② 시작 노드 : 2ᵏ ➔ 2³ = 8 ③ 리프 노드에 원본 ..