개발일지

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