CODEWITHSUNDEEP
arraysalgorithmcount
user78451
user78451

Reputation: 43

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

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

Upvotes: 4

Views: 242

Answers (2)

Gary Ye
Gary Ye

Reputation: 887

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;
}

Upvotes: 4

nevets
nevets

Reputation: 4818

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.

Upvotes: 0

Related Questions