세그먼트 트리와 인덱스드 트리는 뭐가 다른걸까
https://book.acmicpc.net/ds/segment-tree
세그먼트 트리
누적 합을 사용하면, 1번 연산의 시간 복잡도를 $O(1)$로 줄일 수 있습니다. 하지만, 2번 연산으로 수가 변경될 때마다 누적 합을 다시 구해야 하기 때문에, 2번 연산의 시간 복잡도는 $O(N)$입니다.
book.acmicpc.net
https://www.acmicpc.net/blog/view/21
펜윅 트리 (바이너리 인덱스 트리)
블로그: 세그먼트 트리 (Segment Tree) 에서 풀어본 문제를 Fenwick Tree를 이용해서 풀어보겠습니다. Fenwick Tree는 Binary Indexed Tree라고도 하며, 줄여서 BIT라고 합니다. Fenwick Tree를 구현하려면, 어떤 수 X
www.acmicpc.net
사실 인덱스 트리의 종류 중 하나가 세그먼트 트리이다.
'study > 알고리즘' 카테고리의 다른 글
| [TIL] LIS(최장증가수열) 에 대한 공부 (1) | 2023.11.09 |
|---|---|
| [TIL] LinkedList 로 구현한 stack (0) | 2023.10.29 |
| [알고특] backtracking (0) | 2023.07.26 |
| [TIL] 16 시간복잡도 (0) | 2023.07.03 |
| [TIL] 15 DFS & BFS (0) | 2023.07.02 |
