arrays - 查询数组中索引范围 i,j 中 A[i],A[j] 范围内的值

Question

假设我们有一个包含 n 个元素的数组(未排序)。给定一个带有两个参数 i 和 j 的查询，其中 i 和 j 是数组的索引，我想返回值 x st 的数量。 x 在 A[i],A[j] 范围内(独占)并且 x 本身在索引范围内 i<indexof(x)<j .

例如数组是[3,6,7,1,2,4,9,1]

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

所以从索引 1 到 7 的范围 3,9 内的值是

6,7,4

这会产生 3 个值。

我确实需要做一些预处理，以便我可以在 O(logn) 时间内回答查询。 我尝试使用 Fenwick 树解决这个问题，但我想它需要一些修改，而且我不需要对数组进行任何更新，而只需回答查询。

编辑:O(n^2) 和 O(1) 查询的预计算对我来说不是一个有效的选项

Answer 1

可以通过使用与归并排序相关的线段树来解决这个问题。在范围[l,r]对应的每个节点处，该节点存储的数组将是A[l...r]排序后的数组。我们可以在 O(n log n) 时间内对其进行预处理，空间复杂度也将为 O(n log n)，因为每个元素在树的每个高度只出现一次，等于 O(log n)。

构建这棵树的简单方法是使用 O(n log n) 算法对数组的每个节点进行排序，该算法的总时间复杂度为 O(n log^2 n)。但是我已经提到这个过程看起来像合并排序，所以我们可以使用相同的过程来获得 O(n log n) 构建时间的时间复杂度。

例如，让我们考虑示例数组 [3, 6, 7, 1] 的前四个元素。我描述的树将如下所示:

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

现在，如果您对相应节点处的元素进行二分查找，则查询可以在 O(log^2 n) 时间内完成。

构建时间:O(n log n)

查询时间:O(log^2 n)

编辑(用C++构建树的代码，查询留作练习):

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