목록펜윅트리 (2)

개발일지

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 - 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