Querying values within range A[i],A[j] in index range i,j in an array

Question

Suppose we have an array of n elements(unsorted). Given a query with two parameters i and j where i and j are indexes to the array, I want to return the number of values x st. x is within range A[i],A[j](exclusive) and x is itself in index range i<indexof(x)<j.

As an example the array is [3,6,7,1,2,4,9,1]

i=1 j=7
A[i]=3 A[j]=9

so values within range 3,9 from index 1 to 7 are

6,7,4

which results in 3 values.

I definitely need to do some preprocessing so that I can answer the query in O(logn)time. I tried to solve this using a Fenwick tree, but I guess it needs some modification and plus I do not need to do any updates on the array, but just answer queries.

Edit: Precomputing of O(n^2) and O(1) query is not a valid option for me

what's your expected runtime for pre-processing? and what's the range for a[i]? — nevets
– nevets, Commented Sep 7, 2014 at 12:32

Gary Ye · Accepted Answer · 2014-09-07 13:10:44Z

4

One can solve this by using a merge sort related segment tree. At each node corresponding to the range [l, r], the array stored in this node will be the sorted array of A[l...r]. We can preprocess this in O(n log n) time and the space complexity will also be O(n log n) since each element appears only one time at each height of the tree, which is equal to O(log n).

The naive approach to build this tree is to sort the array at each node with an O(n log n) algorithm which gives you a total time complexity of O(n log^2 n). But I've already mentioned that this procedure looks like merge sort, so we can use the same procedure to obtain a time complexity of O(n log n) building time.

For example let's consider the first four elements of your example array [3, 6, 7, 1]. The tree I described will look like this:

    [1,3,6,7]
       /    \ 
  [3,6]     [1,7]
   / \       / \
 [3]  [6]  [7] [1]

Now queries can be done in O(log^2 n) time if you binary search the elements at the corresponding node.

Building time: O(n log n)

Query time: O(log^2 n)

Edit (code for building the tree in C++, querying is left as an exercise):

#include <vector>
using namespace std;
const int MAX_N = 10000;

int A[MAX_N], N; // the array of the integers
vector<int> T[MAX_N * 4];

void merge(vector<int>& C, vector<int>& A, vector<int>& B){
  int i = 0, j = 0, n = A.size(), m = B.size();
  C.assign(n + m, 0);
  while(i < n || j < m){
    if(i == n) C[i + j] = B[j], j++;
    else if(j == m) C[i + j] = A[i], i++;
    else {
      if(A[i] <= B[j]) {
        C[i + j] = A[i];
        i++;
      } else {
        C[i + j] = B[j];
        j ++;
      }
    }
  }
}

void build(int n, int L, int R){
  if(L == R) T[n] = vector<int>(1, A[L]);
  else {
    build(n * 2, L, (L + R) / 2);
    build(n * 2 + 1, (L + R) / 2 + 1, R);
    merge(T[n], T[n * 2], T[n * 2 + 1]);
  }
}

int main(){
  N = 4;
  A[0] = 3, A[1] = 6, A[2] = 7, A[3] = 1;
  build(1, 0, N - 1);
  return 0;
}

edited Sep 7, 2014 at 13:10

answered Sep 7, 2014 at 13:03

Gary Ye

8871 gold badge7 silver badges9 bronze badges

Sign up to request clarification or add additional context in comments.

9 Comments

Evgeny Kluev Over a year ago

Nice solution. And you could improve query time to O(log N) with fractional cascading.

user78451 Over a year ago

thanks. One thing I did not get in querying is that,(going from the example), the nodes will correspond to sorted arrays with certain indexes. In the example, 1-4, 1-2 3-4 , 1-1 2-2 3-3 4-4. So I do not understand what to do if i.e the query is 2-4 as there is no direct corresponding node.

Gary Ye Over a year ago

We will do the queries at node 2-2 and 3-4 and add the results up. There are at most log(n) such nodes we have to do binary search, thus an O(log^2(n)) time complexity. Apparently one can speed this up with fractional cascading, but I haven't checked this out.

user78451 Over a year ago

ok thanks I will try O(log^2(n)) first and see. Perhaps that will be enough

David Eisenstat Over a year ago

@user78451 The constants on fractional cascading aren't wonderful; I wouldn't expect much of a speedup if any.

|

nevets · Accepted Answer · 2014-09-07 12:58:04Z

0

It's can be solved by Fenwick's tree. First let's do it under an assumption that all integers are smaller than 10^6.

The problem that prevents you from using Fenwick's directly is: if your queries come after you finished Fenwick's Tree setup, querying (a[i], a[j]) will involve some numbers a[k] that k > j to be counted. A solution to this is to sort the queries based on its right side, and complete all queries with right index j right after you complete a Fenwick update of a[j]. This will ensure that the numbers come from later index won't affect previous count.

If all numbers are within integer range, map them downto [1..N], where N is the size of your array before you start the routine mentioned above.

The overall complexity will be O(Q log Q + Q log N), where Q is the number of queries, and N is the size of your array.

edited Sep 7, 2014 at 12:58

answered Sep 7, 2014 at 12:39

nevets

4,87826 silver badges42 bronze badges

2 Comments

user78451 Over a year ago

yeah this sounds reasonable and not that hard to implement. But what about the values a[k] that are in the range (a[i],a[j]) and k<i? Because as far as I know Fenwick is for the whole array and we still have the left part k<i to be taken care of right?

nevets Over a year ago

you need to subtract them, i.e. Fenwick_Sum(a[j]) - Fenwick_Sum(a[i] - 1).

Collectives™ on Stack Overflow

Querying values within range A[i],A[j] in index range i,j in an array

2 Answers 2

9 Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

9 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related