How to determine how many elements from a range are within another given range?

Question

I need a little help trying to figure out something:

Given a sequence of unordered numbers (less than 15,000) - A - I have to answer Q queries (Q <= 100000) of the form i, j, x, y , which are translated as follows:

How many numbers in the range [i, j] of A are greater (or equal) than x but less than y with all numbers in the sequence less than 5000.

It seems to me that this requires something like O (logN) due to the large length of the sequence, and it made me think about BIT (binary indexed trees - due to queries), but 2D BIT is too large and takes a long time to run even on the upgrade side. Therefore, the only solution that I see here should be 1D BIT or Segment Trees, but I cannot figure out how to develop a solution based on these data structures. I tried to save the positions in an ordered set of numbers, but I can’t figure out how to make a BIT that answers the requests of this form.

Also, the algorithm should correspond as 500 ms for the given limits. Change 1: 500 ms for all preprocessing operations and respond to requests

EDIT 2: Where i, j are the positions of the first and last element in sequence A to search for elements greater than x and less than y

EDIT 3: Example: Let there be 1, 3, 2, 4, 6, 3 and query 1, 4, 3, 5, so between items 1 and 4 (inclusive) there are 2 elements (3 and 4) more (or equal) than 3 and less than 5

Thank you in advance! PS: Sorry for poor English!

Answer 1

Implement 2D range counting by creating an array of sorted subarrays organized by the BIT. For example, at the entrance

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

the oracle will

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

The use of space is O (N log N) (hopefully great). The design takes O (N log N) if you are careful, or O (N log ^ 2 N) if not (there is no reason to use your application).

To respond to a query with maxima on the sequence index and value (four of them can be used to answer input queries), perform the BIT reading procedure for the maximum index using a binary search in the array to calculate the number of elements not exceeding the maximum value. The request time is O (log ^ 2 N).