thisisuser's study

  • 홈
  • 태그
  • 방명록

hld 1

Heavy-Light Decomposition

Heavy-Light Decomposition이란 트리를 여러 개의 선형 구조로 분해하여 접근할 수 있게 해주는 기법입니다.먼저 트리 위에서 다음과 같은 쿼리가 주어지는 문제를 생각해 봅시다.정점 i의 가중치를 v로 변경한다.두 정점 간의 경로 상의 정점의 가중치 합을 구한다.당연히? $N \le 100000$ 정도입니다.배열 위에서였다면 바로 신나게 세그먼트 트리를 짰겠지만, 트리 위이다 보니 바로 적용하기는 어렵습니다. 배열에서는 되고, 트리에서는 안 되는 이유는 무엇일까요?당연한 소리지만, 트리는 배열과 달리 비선형구조이기 때문입니다. 그렇다면 이렇게, 트리를 여러 개의 선형 구조로 쪼갠다면 어떨까요?이 경우에는 부분 부분에 대해서는 세그먼트 트리로 관리해줄 수 있겠다는 생각이 듭니다.문제는 이걸 ..

Problem Solving 2024.05.21
이전
1
다음
더보기
프로필사진

공부할 거 이것저것

  • 분류 전체보기 (34)
    • Problem Solving (22)
    • 과학고 조기졸업 과제 (10)
      • AP 프로그래밍과 문제해결 (5)
      • 정보과학 융합탐구 (5)
    • 수학 (2)
solved.ac codeup

Copyright © Kakao Corp. All rights reserved.

티스토리툴바