펜윅 트리를 활용한 역쌍 계산 알고리즘
역쌍(Inversion Pair)이란 주어진 양의 정수 배열에서 인덱스 i가 j보다 작으면서 값은 a[i]가 a[j]보다 큰 경우, 즉 i < j && a[i] > a[j]를 만족하는有序对(순서쌍)를 의미한다.
这类 문제를 풀 때 가장 먼저 떠올리는 방법은 병합 정렬을 이용하는 것이다. 그러나 今回は 펜윅 트리(Fenwick Tree) 또는 BIT(Binary Indexed Tree)라는 자료구조를 활용하여 ...
7월 25일 03:34에 게시됨