Làm thế nào để xác định có bao nhiêu phần tử từ một phạm vi nằm trong một phạm vi nhất định?

Question

tôi cần một chút giúp đỡ cố gắng tìm ra một cái gì đó:

Cho một chuỗi các có thứ tự số (dưới 15.000) - Một - Tôi phải trả lời Q truy vấn (Q < = 100000) có dạng i, j, x, y rằng dịch như sau:

có bao nhiêu số trong phạm vi [i, j] từ A lớn hơn (hoặc bằng) so với x nhưng nhỏ hơn y với tất cả số trong t Tôi đang theo ấn tượng này đòi hỏi một cái gì đó như O (logN) vì chiều dài lớn của trình tự và điều này đã cho tôi suy nghĩ về BIT (cây lập chỉ mục nhị phân - vì các truy vấn) nhưng một 2D BIT quá lớn và đòi hỏi nhiều thời gian để chạy ngay cả ở phía cập nhật. Vì vậy, giải pháp duy nhất tôi thấy ở đây phải là 1D BIT hoặc Phân đoạn cây nhưng tôi không thể tìm ra cách giải quyết một giải pháp dựa trên các cấu trúc dữ liệu này. Tôi đã cố gắng giữ lại các vị trí trong tập hợp các số đã đặt hàng nhưng tôi không thể tìm ra cách tạo ra một BIT phản hồi các truy vấn của biểu mẫu đã cho.

Thuật toán cũng phải phù hợp như 500ms cho các giới hạn nhất định. Sửa 1: 500ms cho tất cả các hoạt động trên tiền xử lý và trả lời các truy vấn

EDIT 2: đâu i, j là vị trí của phần tử đầu tiên và cuối cùng trong dãy A đến tìm kiếm yếu tố lớn hơn x và nhỏ hơn y

EDIT 3: Ví dụ: Let there be 1, 3, 2, 4, 6, 3 và truy vấn 1, 4, 3, 5 nên giữa vị trí 1 và 4 (bao gồm) có 2 các phần tử (3 và 4) lớn hơn (hoặc bằng) lớn hơn 3 và nhỏ hơn 5

Cảm ơn bạn trước! Tái bút: Xin lỗi vì tiếng Anh nghèo nàn!

Answer 1

Thực hiện đếm dải 2D bằng cách tạo một mảng con được sắp xếp theo BIT. Ví dụ, trên đầu vào

[1, 3, 2, 4, 6, 3] 

oracle sẽ

[[1] 
,[1, 3] 
,[2] 
,[1, 2, 3, 4] 
,[6] 
,[3, 6] 
]. 

Việc sử dụng không gian là O (N log N) (hy vọng tốt). Xây dựng có thời gian O (N log N) nếu bạn cẩn thận, hoặc O (N log^2 N) thời gian nếu không (không có lý do để được cho ứng dụng của bạn methinks).

Để trả lời truy vấn có giá trị và giá trị chuỗi tối đa (bốn trong số này có thể được sử dụng để trả lời truy vấn đầu vào), thực hiện quy trình đọc BIT cho chỉ mục tối đa, sử dụng tìm kiếm nhị phân trong mảng để đếm số các phần tử không vượt quá giá trị tối đa. Thời gian truy vấn là O (log^2 N).