ITPE * JackerLab

개요Heavy-Light Decomposition(HLD)은 트리 구조에서 경로 쿼리(Query)나 업데이트(Update)를 빠르게 처리하기 위해 고안된 분할 기법입니다. 트리의 간선을 무거운(Heavy) 간선과 가벼운(Light) 간선으로 분류하여, 경로를 소수의 구간(segment)으로 분해하고, 각 구간에 대해 세그먼트 트리(Segment Tree)나 펜윅 트리(Fenwick Tree) 같은 자료구조를 적용하여 O(log² n) 또는 O(log n) 시간 복잡도로 효율적인 처리를 가능하게 합니다.1. 개념 및 정의 항목 내용 정의트리를 Heavy 간선과 Light 간선으로 분할하여 경로 쿼리와 업데이트를 최적화하는 알고리즘적 테크닉목적트리 경로 질의의 시간 복잡도를 개선하여 고속 연산 지원필요성단..

개요Fenwick Tree는 Binary Indexed Tree라고도 불리며, 배열 상의 누적 합(부분합, prefix sum)을 빠르게 계산하고 업데이트할 수 있는 효율적인 자료구조입니다. 주로 누적합 쿼리와 단일 원소 갱신이 빈번히 발생하는 문제에서 사용되며, 시간 복잡도 O(log n)으로 빠른 성능을 제공합니다.1. 개념 및 정의 항목 내용 정의배열 상의 누적 합을 빠르게 질의(query)하고, 업데이트(update)할 수 있도록 설계된 트리 기반 자료구조목적부분합 계산과 값 갱신을 모두 O(log n) 시간에 처리필요성단순 배열 누적합은 쿼리는 빠르지만 갱신이 느리고, 세그먼트 트리는 구현이 복잡함Fenwick Tree는 구현 단순성과 빠른 성능을 동시에 제공하는 최적화된 선택지입니다.2. 특..