게으름뱅이의 앞구르기

트리구조로 구간 합 구하기 세그먼트 트리는 구현하는 과정이 복잡하고 어려움 → 인덱스 트리는 구현이 매우 간단하며 O(logN)의 시간 복잡도를 가짐 인덱스 트리는 세그먼트 트리에 비해 메모리 효율성이 높음 특정 숫자의 마지막 비트를 구함(A & -A) 각 인덱스의 마지막 비트를 내가 저장하고 있는 값들의 개수로 계산 마지막 비트만큼 구간을 앞으로 이동하며 합을 구함 참고 | Wikipedia, Fast campus 컴퓨터 공학 전공 필수

세그먼트 트리로 구간합* 구하기 선형적으로 구간합을 구하면 O(N)의 시간 복잡도를 가지므로 비효율적임 트리구조를 이용하여 구간합을 구하여 O(logN)의 시간복잡도로 구간합을 구함 *구간합 : 여러개의 데이터가 연속적으로 존재할 때 특정한 범위의 데이터 합을 구하는 것 완전 이진 트리에 데이터 삽입 구간 합 트리 생성(특정 범위 인덱스의 값을 저장함) 필요한 구간에 포함된 트리 노드의 값들로 구간합을 계산함 참고 | Wikipedia, Fast campus 컴퓨터 공학 전공 필수