Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 |
Tags
- Transport layer
- 네트워크
- 전송 계층
- Application Layer
- 응용 계층
- Embedded
- boot sequence
- 프로그래머스
- 부트시퀀스
- leetcode
- 데이터베이스
- Database
- baekjoon
- Network
- Djikstra
- dp
- STL
- 문제풀이
- ps
- 백준
- BST
- 임베디드
- 관계형 모델
- BHS
- swea
- 다익스트라
- 자료구조
- DB
- C++
- 릿코드
Archives
- Today
- Total
목록인덱스 트리 (1)
BOBO's Note
Segment Tree와 Indexed Tree
세그먼트 트리는 어떠한 배열이 주어졌을 때, 각 구간의 대표값(예. 합, 최대값 등)을 빠르게 구할 수 있는 자료구조이다. 배열의 크기가 N일 때, 임의의 구간에 대한 쿼리를 O(logN)에 수행할 수 있다. 인덱스 트리는 팬윅 트리(Fenwick Tree)라고도 하며, 세그먼트 트리처럼 각 구간의 대표값을 빠르게 구할 수 있다. 세그먼트 트리보다 구현하기 더 간단하고 속도가 빠르다는 장점이 있다. 이 포스터에서는 구간합을 세그먼트 트리를 이용해 빠르게 구하는 방법에 대해 알아보자. 구간합 구하기 배열 arr[0], arr[1], ..., arr[N-1]이 있다고 할 때, 임의의 구간 [l, r]에 대하여 구간합 arr[l] + arr[l+1] + ... + arr[r-1] + arr[r]을 구해라. 위..
Algorithm
2020. 8. 16. 16:51