Phạm vi truy vấn số đảo ngược trong thời gian O (lg N)

Question

Với một mảng không được phân loại của n số nguyên, tôi biết tôi có thể tìm ra tổng số đảo sử dụng BIT trong thời gian O (N lg N) sau phương pháp này: Count Inversion by BIT

Tuy nhiên có thể nếu tôi phải truy vấn một phạm vi tùy ý cho tổng số nghịch đảo trong O (lg N)?

Tính toán trước O (N lg N) có thể chấp nhận được.

Tôi đã thực hiện một số nghiên cứu và dường như yếu tố N không thể tránh được ... Mọi đề xuất sẽ được đánh giá cao!

Answer 1

Đây không phải là câu trả lời mà bạn đang tìm kiếm, nhưng tôi có hai đề xuất.

Trước tiên, tôi không nghĩ rằng BIT là cấu trúc dữ liệu phù hợp để sử dụng cho vấn đề bạn đang cố giải quyết. Lợi thế của BIT là nó duy trì tổng tiền tố có thể truy vấn O (lg n) chỉ sử dụng O (lg n) cho mỗi lần chèn. Vì bạn không chèn khi cấu trúc dữ liệu của bạn được hoàn thành, BIT không thuận lợi (vì bạn có thể sử dụng một mảng tiền tố đơn giản, có thể truy vấn được trong O (1)).

Thứ hai, tôi có một thuật toán ngây thơ có sử dụng O (n) thời gian và không gian để xây dựng một cấu trúc dữ liệu có thể tìm thấy đảo phạm vi trong thời gian O (1) thời gian:

Thứ nhất, xây dựng một (n X n) ma trận ánh xạ các đảo ngược, sao cho chỉ mat[i][j]=1 nếu i<j và arr[i] và arr[j] được đảo ngược. Sau đó, tính tổng tiền tố trên mỗi hàng của ma trận này, sao cho mat[i][j] là số lần đảo ngược có liên quan đến arr[i] trong phạm vi [i,j]. Cuối cùng, tính tổng hậu tố trên mỗi cột, sao cho mat[i][j] là tổng số nghịch đảo trong phạm vi [i,j].

for i from 0 to n-2 
    for j from i+1 to n-1 
    if(arr[j] > arr[i]) 
     mat[i][j] = 1; 
for i from 0 to n-2 
    for j from i+1 to n-1 
    mat[i][j] += mat[i][j-1]; 
for j from n-1 to 1 
    for i from j-1 to 0 
    mat[i][j] += mat[i+1][j]; 

này có rõ ràng O (n) thời gian và không gian, nhưng số lượng đảo trong bất kỳ phạm vi có thể được truy vấn trong thời gian liên tục.