Segment tree (1) 썸네일형 리스트형 Efficient Range Minimum Queries using Binary Indexed Trees 주제 : 역원이 존재하지 않는 연산에 대한 구간 쿼리 (펜윅 트리) 펜윅트리에서 요구하는 연산을 $, 이 연산의 역원을 #라고 정의하겠습니다. 흔히 펜윅트리에서 구간 [L, R]에 대한 쿼리를 처리할 때는 ([1, R] 쿼리의 답) # ([1, L) 쿼리의 답)과 같은 형태로 답을 구합니다.$이 +라고 한다면 #은 -로 ([1, R] 쿼리의 답) - ([1, L) 쿼리의 답)을 의미합니다. 역원이 존재하지 않는 연산은 어떻게 처리해야할까요?그 예로 \( min(a, ?) = \infty \)를 만족하는 ?는 존재하지 않기 때문에min에는 역원이 존재하지 않습니다.그래서 일반적인 형태의 펜윅 트리로는 구간 [L, R]의 min값을 구할 수 없습니다. 이제 펜윅트리로 range rmq 문제를 해결하는 방.. 이전 1 다음
