Readiz구간 자료구조 · 강의
구간 자료구조
3개 문서모든 날짜의 글 · 날짜를 누르면 아래 목록에 표시됩니다.
3개 문서
| 문서 | 게시일 |
|---|---|
좌표와 구간 합을 관리하는 자료구조좌표 압축, Fenwick과 Segment Tree로 값과 구간 정보를 관리한다. 선수 지식 · 정렬, lower_bound와 누적합의 이해 | |
| 1.좌표 압축: 순서는 남기고 값의 크기는 줄이기 큰 값과 중복을 작은 인덱스로 바꾸고, 순위 차이와 실제 거리의 차이를 확인합니다. 구간 자료구조 | |
| 2.Fenwick Tree: 바뀌는 배열의 구간 합 누적합을 다시 만들지 않고, 점 갱신과 구간 합을 로그 시간에 처리합니다. 구간 자료구조 | |
| 3.Segment Tree: 구간 합과 미룬 갱신 점 대입에서 구간 덧셈까지, 노드의 합과 lazy 값을 함께 추적합니다. 구간 자료구조 | |
분류 기준 · 문서 안내
기존 글은 원래 분류를 유지하고, 새 글은 중심 주제로 폴더를 고릅니다. 상위 폴더에는 하위 폴더의 글도 함께 표시됩니다.