Euler Tour Technique (1) 썸네일형 리스트형 166. Euler Tour Technique 지금까지 수열에서 구간 업데이트와 구간 합을 구하기 위해 세그먼트 트리를 사용하였다. 이번에는 이것을 일반적인 트리 구조에 적용해 볼 것이다. 오일러 투어 테크닉(오일러 경로 테크닉, Euler Tour Technique, ETT)은 세그먼트 트리에서 일자형 구조에 사용한 기술을 트리 구조에 적용할 때 사용되는 방법으로 다음과 같은 쿼리들을 처리할 수 있게 해 준다. 노드마다 값을 하나씩 가진다고 하자. 노드 $v$에 할당된 값을 변경한다. 노드 $v$를 루트로 하는 서브트리의 각 노드에 할당된 값을 변경한다. 노드 $v$에 할당된 값을 출력한다. 노드 $v$를 루트로 하는 서브트리의 각 노드에 할당된 값의 합(최대, 최소 등 다양하게 변경할 수 있음)을 출력한다. 즉 노드 쿼리나 서브트리 쿼리를 처리할.. 이전 1 다음
