개발일지

개념 각 노드에 구간의 정보를 저장하여 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 참..

개념 각 인덱스는 최하위 비트의 값만큼 구간을 저장하고 이를 이용하여 구간의 합을 빠르게 찾을 수 있다. => 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..