목록segment tree (3)

개발일지

Algorithm in A..Z - Lazy Segment Tree

개념 Segment Tree에서 구간의 Update를 빠르게 처리하기 위한 방법이다. Segment Tree에서 Update의 시간 복잡도는 O(logN)이기 때문에 구간의 길이가 L인 Update의 시간 복잡도는 O(LlogN)이기 때문에 쿼리의 수가 많은 경우 시간초과를 받을 수 있다. Lazy Segment Tree는 Update를 필요한 시기에 Update하도록 미루면서 Range Update를 O(logN)으로 수행할 수 있다. 작동원리 구간을 Update할 경우 Segment Tree에서 참조하는 Node만 Update를 진행하고, 자식 노드의 Update는 Lazy Tree에 기록하여 Update를 미룬다. 시간 복잡도 init : O(NlogN) update : O(logN) update_..
Algorithm (알고리즘) 2021. 3. 4. 02:24
Algorithm in A..Z - Segment Tree

개념 각 노드에 구간의 정보를 저장하여 Query, Update를 빠르게 처리할 수 트리다. 작동원리 트리로 구간의 정보를 저장하여 최악의 경우 트리의 높이만큼 트리를 탐색하여 Query와 Update를 수행할 수 있다. 트리의 성질 왼쪽 자식노드 : index * 2 오른쪽 자식노드 : index * 2 + 1 Query 참조하는 범위가 구간을 완전히 벗어나면 0을 Return한다. 참조하는 범위가 구간에 완전히 겹치면 Tree에 저장된 값을 Return한다. 참조하는 범위가 구간에 걸치면 Tree에 더 깊은 Level을 참조한다. 3-6 구간의 정보를 얻으려면 5, 6을 참조한다. 1-7 구간의 정보를 얻으려면 2, 6, 14를 참조한다. 1-8 구간의 정보를 얻으려면 1을 참조한다. Update 참..
Algorithm (알고리즘) 2021. 3. 2. 18:52
Algorithm in A..Z - Fenwick Tree(Binary Indexed Tree)

개념 각 인덱스는 최하위 비트의 값만큼 구간을 저장하고 이를 이용하여 구간의 합을 빠르게 찾을 수 있다. => 1, 3, 5, 7은 최하위 비트의 값이 1 -> 구간의 길이가 1만큼의 합을 저장 => 2, 6은 최하위 비트의 값이 2 -> 구간의 길이가 2만큼의 합을 저장 => 4는 최하위 비트의 값이 4 -> 구간의 길이가 4만큼의 합을 저장 => 8은 최하위 비트의 값이 8 -> 구간의 길이가 8만큼 합을 저장 작동원리 최하위 비트를 구하는 법 index & -index Query 1-3 구간의 합을 구하면 트리에서 2, 3을 더한다. 3(0011)에 저장된 값을 더하고 최하위 비트(0001)를 뺀다. => 2(0010) 2(0010)에 저장된 값을 더하고 최하위 비트(0010)를 뺀다. => 0(0..
Algorithm (알고리즘) 2021. 3. 2. 18:05
Prev 1 Next