Algorithm 공부 #21 - 세그먼트 트리
Algorithm 공부 #21 - 세그먼트 트리 세그먼트 트리(Segmant Tree) ● 주어진 제이터의 구간 합과 데이트 업데이트를 빠르게 수행하기 위한 알고리즘 ● 트리 초기화 / 질의값 구하기(구간 합 구하기, 최대, 최소) / 데이터 업데이트하기의 과정으로 나뉨 ● 트리 초기화하기 1. 데이터의 개수가 2^k일때 start_index=2^k 2. 2^k+1 인덱스부터 리프노드를 제외한 나머지 노드의 값을 채우기 3. 구간 합일 때 : A[N] = A[2N] + A[2N+1] / 최대 : A[N] = max(A[2N], A[2N+1) 최소 : A[N] =min(A[2N],A[2N+1]) ● 질의값 구하기 1. 질의 인덱스를 세그먼트 트리 인덱스로 변환 => 세그먼트 트리 index = 주어진 질의..
Algorithm/알고리즘 공부 일기
2024. 3. 16. 19:30
반응형
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- 알고리즘
- 자료구조
- HTML5
- 자바
- html
- DFS
- 카운팅 정렬
- 우선순위 큐
- C++ Stack
- 스택
- BFS
- 에라토스테네스의 체
- 유니온 파인드
- 스프링 부트 crud 게시판 구현
- 이분 매칭
- 유클리드 호제법
- CSS
- java
- js
- 알고리즘 공부
- Do it!
- C++
- 투 포인터
- 세그먼트 트리
- 자바스크립트
- DP
- c++ string
- 백준 풀이
- 반복문
- 백준
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
글 보관함