펜윅트리(Fenwick tree) 자바 구현 예시

펜윅트리(Fenwick tree)는 세그먼트 트리에서 조금 더 진화된 버전입니다. 사용처는 연속된 구간의 합을 구할 때 사용하면 빠르고 효율적인 계산을 할 수 있습니다. 복잡도는 O(log n)의 복잡도를 가집니다. 이진 트리 인덱스라고도 하는데, 이진수의 성질을 이용해서 트리를 구현했기 때문입니다. 펜윅트리의 기능은 두 가지가 있는데 합과 갱신 입니다. 그림으로 어떻게 돌아가는지를 보면 다음과 같습니다. 아래 그림처럼 생각하면 됩니다. 위에가 인덱스이고 아래가 마지막 2진수의 위치입니다. 만약 13까지의 합을 구하려면 8까지의 합 + 12까지의 합 + 13까지의 합을 구하면 됩니다. 갱신을 할 때도 13을 갱신할 때 12부분과 8부분을 갱신해줘야 합니다. 이를 자바 함수로 구현하면 다음과 같습니다. 합을 구하기 public static long sum(int[] tree, int i) { long ans = 0; while (i > 0) { ans += tree[i]; i -= (...

원문링크 : 펜윅트리(Fenwick tree) 자바 구현 예시