가장자리 트리(지속 가능한 세그먼트 트리) 기초 설명
개요
가장자리 트리는 지속 가능한 세그먼트 트리로, 하지타 님이 개발한 데이터 구조이다. 함수형 세그먼트 트리라고도 불린다. 이 구조는 배열의 역사적 상태를 효율적으로 저장하고 조회할 수 있게 해준다.
핵심 아이디어
모든 버전을 복제하는 방식은 메모리 낭비가 심하다. 하지만 각 업데이트에서 영향을 받는 노드는 루트까지의 경로에 국한된다. 따라서 기존 트 ...
9월 9일 16:17에 게시됨
CDQ 분할 정복 기법을 활용한 다차원 쿼리 처리
CDQ 분할 정복 개요
CDQ 분할 정복은 복수의 쌍 (i, j)에 대해 왼쪽 구간과 오른쪽 구간 간의 상관 관계를 효율적으로 계산하는 기법입니다. 이는 주로 순서가 중요한 쿼리 문제에서 사용되며, 분할과 정복 과정 중에 왼쪽 데이터가 오른쪽 데이터에 미치는 영향을 집계합니다.
문제 예시: 3차원 편향 쿼리 (P3810)
각 요소는 세 가지 차원 a, b, c로 구성되며, 조건 a_i ...
6월 27일 17:05에 게시됨