A collection of 92 articles on programming, technology and life.
Concept [[Segment Tree]]에서 배열의 구간의 변화가 생길 때, 이를 효율적으로 처리하기 위한 후속 자료구조이다. Lazy Segment Tree의 핵심은 이다. 즉, Lazy Segment는 구간의 변화가 생길 때 그 값을 즉시 갱신하는 것이 아닌 후에 해당 Node를 방문했을 때 갱신한다. 쉽게 말해, 구할 범위가 아닌 값에 굳이 업데이트를 해 시간을 낭비하는 것 아니라 이를 뒤로 미루는 것이 Lazy Segment Tree의 핵심이다. 일반적인 Segment Tree에
Concept 에 Edge을 'Heavy Edge'와 'Light Edge'로 나누어 구분하는 알고리즘이다. 부모 Node($u$)와 u의 자식 Node($v$)를 있는 Edge($e$)가 있을 때, v의 Sub Tree 크기가 u의 Sub Tree 크기의 1/2 이상일 때 를 Heavy Edge라 정의하며 이 이외에는 모두 Light Edge이다. 라 정의하면 는 $Size[v] >= Size[u
Concept 라고도 불린다. [[Segment Tree]]의 변형 트리로 구간의 합을 빠르게 구할 수 있다는 특징이 있다. 시간복잡도는 Segment Tree와 같은 $O(log{N})$이지만 공간복잡도는 $O(n)$으로 Segment Tree보다 더 적다. 시간복잡도 자체는 Segment Tree와 같다고 해도 실제론 조금 더 빠르게 작동하게 되는데 선형적으로 $Lazy Segment Tree ≒ 2 * Segment Tree / Segment Tree ≒ 2
Concept 특정 노드(Node)의 모든 하위 Node 또는 상위 Node에 대한 쿼리를 처리하고자 할 때, 사용하는 알고리즘이다. List와 다르게 Tree는 구간의 연속성을 가지지 않는다. 따라서 구간에 대한 쿼리를 처리하기 어렵다. 이를 해결하기 위해 [[DFS(Depth-First Search)]]을 사용하여 Tree의 서브 트리 구간을 List 형태로 만들어 구간에 대한 정보를 처리한다. Euler Tour Technique 그 자체만으로 문제를 해결하는 경우는 거의 없고 [[Segment Tree]]
Concept Trie는 Retrieval Tree(탐색 트리) 이름에서 따온 말로, 문자열을 저장하고 효율적으로 탐색하기 위한 Tree이다. Radix Tree, Prefix Tree라고도 불린다. 문자열을 저장하는 측면에서 각 노드들이 자식 포인터 배열을 가지고 있다는 점에서 메모리 측면에서는 좋지 않지만 여러 문자열들을 탐색할 때 시간복잡도가 작다. 문자열의 하나하나의 문자를 [[DFS(Depth-First Search)]]로 노드에 넣고 이를 이어서 하나의 Tree를 만든다. 문자열들의 개수를 M,