Как найти уникальные цифры в заданном диапазоне массивов эффективно?

Question

Учитывая массив (не отсортированный) и несколько запросов диапазона. Для каждого запроса мне нужно найти количество уникальных цифр в заданном диапазоне. Вот наивный подход, который я придумал.

#include<cstdio> 
#include<iostream> 
using namespace std; 

int main() 
{ 
    int n; scanf("%d",&n); //Size of the array 
    int a[n+1]; a[0]=0; 

    for(int i=1;i<=n;i++) 
     scanf("%d",&a[i]); 

    int q; scanf("%d",&q); //Number of queries 

    while(q--) 
    { 
     int x,y; scanf("%d %d",&x,&y); //Range of each query 
     int bit[n+1]; 
     for(int i=0;i<=n;i++) 
      bit[i]=0; 

     for(int i=1;i<=n;i++) 
     { 
      for(int j=i-1;j>0;j--) 
      { 
       bit[i]=a[i]; 
       if(bit[j]==a[i]) 
       { 
        bit[j]=0; 
        break; 
       } 
      } 
     } 
     int cnt=0; 
     for(int i=x;i<=y;i++) 
     { 
      if(bit[i]) 
       cnt++; 
     } 
     printf("%d\n",cnt); 
    } 
    return 0; 

} 

Каков наиболее эффективный способ выполнения этой операции? Я думаю, что это можно сделать, используя двоичное индексированное дерево, но не смог найти решение.

Answer 1

Если количество запросов диапазона мала по сравнению с размером массива, скажем, О (к) против O (N), где к < < п, то:

1. поместить все диапазон конечных точек в сбалансированное двоичное дерево O (klogk)
2. Сделайте один проход по массиву и подсчитайте уникальные элементы в каждом поддиапазоне. Используйте хеш-таблицу, чтобы запомнить, какие элементы мы уже видели. O (n)
3. Выполнение обхода между конечными точками диапазона для каждого запроса диапазона и суммарного суммирования сумм. O (k^2) наихудший случай/O (klogk) для разумных запросов.