范围A内查询值[I]，A [j]的索引范围I，J在一个数组 [英] Querying values within range A[i],A[j] in index range i,j in an array

问题描述

假设我们有n个元素（未分类）的阵列。给定的查询与两个参数i和j，其中i和j是索引到阵列中，我想返回值x ST的数量。 x为范围内的 A [1]，A [J] （独家）和x本身在指数范围 I＆LT;的indexOf（X）＆LT; Ĵ。

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.

作为一个例子，数组是 [3,6,7,1,2,4,9,1]

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

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

所以到7范围内的3,9值从指数1为

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

6,7,4

这导致3个值

which results in 3 values.

我肯定需要做一些preprocessing，这样我可以回答O（LOGN）时间查询。 我想这使用的是树状数组来解决，但我想这需要做一些修改，并加上我不需要做阵列上的任何更新，只是回答询问。

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.

编辑：为O（n ^ 2）和O（1）查询是不是对我来说是有效的选项

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

推荐答案

我们可以通过使用合并排序相关线段树解决这个问题。在相应的区间[L，R]的每个节点，存储在此节点的数组会的排序数组并[... R]。我们可以preprocess这为O（n log n）的时间和空间复杂度也会为O（n log n）的，因为每个元素只出现一次的树，等于澳各高（日志N ）。

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).

在幼稚的做法来构建这棵树是在阵列中，每个节点有一个O排序（N log n）的算法，它给你哦的总的时间复杂度（N日志^ 2 N）。但我已经提到过，这个过程看起来像归并排序，所以我们可以用同样的方法来获得Ö的时间复杂度（N 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.

例如，让我们考虑您的示例阵列的前四个元素，[3，6，7，1。我所描述的树将是这样的：

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]

现在的查询可以在O完成（日志^ 2 n）的时间，如果你的二进制搜索，在相应的节点的元素。

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

建筑时间：为O（n log n）的

Building time: O(n log n)

查询时间：为O（log ^ 2 N）

Query time: O(log^2 n)

编辑（code建筑树在C ++中，查询被作为一个练习）：

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

这篇关于范围A内查询值[I]，A [j]的索引范围I，J在一个数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！