펜윅 트리(BIT) 누적합 계산기

i를 2진수로 썼을 때 맨 아래 1비트만 남긴 값입니다. 2의 보수에서 −i는 i의 비트를 뒤집고 1을 더한 값이라 두 수를 AND하면 그 비트만 살아남습니다. 12 = 1100₂이면 12 & (−12) = 100₂ = 4입니다. 펜윅 트리에서 하는 일은 사실상 이 한 줄이 전부입니다.

하는 일이 반대이기 때문입니다. 갱신은 i += i & (−i)로 나를 품는 더 큰 칸으로 올라가며 그 칸들의 값을 고치고, 질의는 i −= i & (−i)로 맡은 구간을 떼어 내며 앞으로 내려갑니다. 부호가 반대인 이 두 줄이 처음 볼 때 가장 헷갈리는 자리입니다.

질의의 걸음 수가 i의 2진수에 있는 1비트의 개수와 같기 때문입니다. 맨 아래 1비트를 하나씩 떼어 내므로 1이 몇 개인지가 곧 걸음 수이고, 그 개수는 자릿수를 넘을 수 없어 log₂n 이하입니다. 13 = 1101₂이면 세 걸음(13 → 12 → 8 → 0)이고, 32처럼 2의 거듭제곱이면 한 걸음이면 끝납니다.

질의만 있다면 그쪽이 낫습니다. 누적합 배열은 질의가 O(1)이지만 값 하나가 바뀌면 그 뒤를 전부 고쳐야 해서 갱신이 O(n)입니다. 펜윅 트리는 둘 다 O(log n)으로 맞춥니다. 값이 자주 바뀌면서 구간 합도 자주 물어야 할 때 값어치가 있습니다.

쓸 수 없습니다. 구간 합 질의가 「r까지의 합 − (l−1)까지의 합」이라는 뺄셈에 기대고 있어서 연산에 역원이 있어야 하는데, 최솟값에는 「빼기」가 없기 때문입니다. min(a, b)를 알아도 a를 되돌릴 수 없습니다. XOR처럼 역원이 자기 자신인 연산은 되고, 곱셈은 0이 끼면 안 됩니다. 구간 최솟값·최댓값이 필요하면 세그먼트 트리를 씁니다.

lowbit(0) = 0이라 0번을 쓰면 갱신 고리가 제자리에 갇히기 때문입니다. i += 0은 i를 그대로 두므로 무한 반복이 됩니다. 그래서 트리 배열은 1번부터 쓰고, 0번 칸은 비워 둡니다.

전송되지 않습니다. 모든 계산은 브라우저 안에서 이뤄지고, 입력값은 이 기기에만 남습니다.