바이너리 인덱스 트리 알고리즘 (펜윅 트리) 백준2042
바이너리 인덱스 트리 알고리즘 (Binary Indexed Tree) i&-i 앤드연산을 이용해 누적합을 계산하는 알고리즘이다. 1&-1 : 1 2&-2 : 2 3&-3 : 1 4&-4 : 4 ... 임을 이용한다. 이렇게 나오는 원리를 알아보면 아래와 같다. i i 2진수 2의 보수 i&-i result 1 00000001 11111111 00000001 1 2 00000010 11111110 00000010 2 3 00000011 11111101 00000001 1 4 00000100 11111100 00000100 4 1 2 1 4 1 8 1 16 1 32 ... 이렇게 나오는 원리를 이용해 각 인덱스별로 값 1개의 합, 값 2개의 합, 값 1개의 합, 값 4개의 합 구간합을 미리 구해놓는다. 백준..
