Đếm đảo ngược bằng cách sử dụng BIT

Question

Tôi biết câu hỏi này đã được thảo luận trước đây, nhưng tôi quan tâm đến việc này bằng cách sử dụng một cây nhị phân lập chỉ mục. Tôi tìm thấy liên kết this để hiển thị cách thực hiện. Tôi không thực hiện theo lời giải thích. Có thể ai đó xin vui lòng cho tôi một lời giải thích về lý do tại sao sau đây đưa ra có sự thật.

Create a BIT of size greater than n(no of elements). Iterate through array A (
let j be the index of loop),and for each element A[j] do: 

1) Add j-sum(A[j]) to the number of inversions 
2) add(A[j], 1) (i.e. add 1 to the position A[j] on BIT. This effectively 
counts the number of time value A[j] is seen so far) 

Tôi không hiểu tại sao lại hoạt động.

Answer 1

Đảo ngược xảy ra khi phần tử lớn hơn một số phần tử theo sau phần tử đó trong mảng.

Chúng tôi có thể đếm nghịch đảo bằng cách nhóm chúng theo yếu tố thứ hai. Ví dụ, trong mảng [4, 3, 1, 2], các cặp phần tử (4, 3), (4, 1), (4, 2), (3, 1) và (3, 2) là đảo ngược. Chúng tôi nhóm chúng theo yếu tố thứ hai, do đó: [[(4, 1), (3, 1)], [(4, 2), (3, 2)], [(4, 3)]].

Chúng tôi xem xét từng phần tử lần lượt và tính số lần đảo ngược nó là phần tử thứ hai của. Trong ví dụ, phần tử 4 là phần tử thứ hai trong 0 nghịch đảo, phần tử đảo ngược 3 trong 1 và các phần tử 1 và 2 trong 2 đảo ngược từng phần tử.

Để cho bất kỳ phần tử nào là phần tử thứ hai của đảo ngược, phải có phần tử lớn hơn ở đâu đó trước đó trong mảng.

Chúng tôi thực hiện đếm hiệu quả bằng cách duyệt qua mảng từ trái sang phải và luôn theo dõi số lượng phần tử của từng giá trị đã gặp phải cho đến nay, bằng cách sử dụng BIT. Ban đầu, bảng tần số của chúng ta sẽ là [0, 0, 0, 0], vì chúng ta không thấy yếu tố nào cả. Sau khi chúng tôi truy cập vào 4, chúng tôi cập nhật tần số của nó, cho [0, 0, 0, 1]. Sau khi truy cập vào 3, [0, 0, 1, 1], v.v.

Mỗi khi chúng tôi ghé thăm một vị trí, chúng tôi sử dụng BIT để tìm hiểu xem có bao nhiêu yếu tố được truy cập cho đến nay lớn hơn nó. Vì vậy, ví dụ khi chúng ta gặp phải 1, BIT hiện có chứa [0, 0, 1, 1], đại diện cho rằng có đến số không 1 và 2, một 3 và một 4. Bằng cách thêm các giá trị 0 + 1 + 1 , chúng tôi tính số lượng các phần tử cho đến nay lớn hơn 1.

Thêm tất cả số lượng cá nhân này cho tổng số lần đảo ngược.

Lưu ý rằng, nói chung, bạn phải sử dụng phối hợp nén để điều này có hiệu quả. Ví dụ, nếu mảng ban đầu của bạn chứa các số như A = [92, 631, 50, 7], bạn không nên cấp phát một BIT với hàng trăm phần tử. Thay vào đó, hãy sắp xếp mảng để xác định rằng 7 631, cho phép chúng tôi gán các cấp bậc 7 => 1, 50 => 2, 92 => 3, 631 => 4; sau đó thay thế từng phần tử theo thứ hạng của nó, cho B = [3, 4, 2, 1]. Số lần đảo ngược của mảng này sẽ giống như trong bản gốc, vì B [i]> B [j] nếu và chỉ khi A [i]> A [j].

(Lưu ý: Một lập trình viên thực sự có thể sẽ sử dụng chỉ mục bắt đầu từ số không.)