펜윅 트리 (BIT)

배열 앞에서부터 어느 칸까지의 합(누적 합)을 구하는 일과 칸 하나의 값을 바꾸는 일을 둘 다 O(log n)에 해 주는 자료구조다. 만든 사람 이름을 따 펜윅 트리라 하고, Binary Indexed Tree 를 줄여 BIT 라고도 부른다.