Interrogazione di intervallo minore#5084

Interrogazione di intervallo minore (Editoriale)

Algoritmo Merge tree. In ogni vertice dell'albero dei segmenti memorizzeremo un array aggiuntivo. Il vertice, corrispondente al segmento fondamentale $[i; j]$ , contiene nel proprio array l'insieme ordinato dei numeri $a_{i}, ..., a_{j}$ a_i, ..., a_j.

La costruzione di un tale albero richiede $O (n l o g_{2} n)$ O(nlog_2n) di tempo, poiché durante l'unione di due vertici figli i loro array ordinati vengono fusi in modo analogo al passo dell'algoritmo di fusione nel merge sort.

Per trovare il numero di elementi nel segmento $[l, r]$ [l, r] che sono minori di $x$ , è necessario suddividere questo segmento in un insieme di segmenti fondamentali dell'albero dei segmenti. Per ciascuno di essi viene eseguita una ricerca binaria nel corrispondente array ordinato, che permette di determinare il numero di elementi minori di $x$ .

Poiché il segmento $[l, r]$ [l, r] viene suddiviso in non più di $O (l o g_{2} n)$ O(log_2n) segmenti fondamentali, e la ricerca binaria in ciascuno di essi viene eseguita in $O (l o g_{2} n)$ O(log_2n), il tempo di elaborazione di una richiesta è $O (l o g_{2}^{2} n)$ O(log_2^2n).

Esempio

Implementazione dell'algoritmo

Dichiariamo l'albero dei segmenti. In ogni suo vertice memorizzeremo un array di numeri.

vector<vector<int> > SegTree;

I numeri in ingresso vengono memorizzati nell'array $a$ .

vector<int> a;

La funzione BuildTree costruisce l'albero dei segmenti a partire dall'array $a$ . L'array ordinato in ogni vertice viene formato fondendo gli array dei suoi vertici figli in tempo $O (n)$ con l'aiuto della funzione merge.

void BuildTree(int v, int lpos, int rpos)
{
  if (lpos == rpos)
    SegTree[v].push_back(a[lpos]);
  else
  {
    int mid = (lpos + rpos) / 2;
    BuildTree(2*v, lpos, mid);
    BuildTree(2*v+1, mid+1, rpos);

    SegTree[v].resize(rpos - lpos + 1);
    merge(SegTree[2*v].begin(), SegTree[2*v].end(), 
          SegTree[2*v+1].begin(), SegTree[2*v+1].end(), 
          SegTree[v].begin());
  }
}

C++

La funzione Query conta il numero di elementi nel segmento $[l, r]$ [l, r] i cui valori sono minori di $x$ . Per ogni segmento fondamentale $[l e f t; r i g h t]$ [left; right], con l'aiuto della funzione $l o w er_b o u n d$ lower\_bound troviamo il numero di elementi minori di $x$ .

int Query(int v, int lpos, int rpos, int left, int right, int x)
{
  if (left > right) return 0;
  if ((lpos == left) && (rpos == right))
    return lower_bound(SegTree[v].begin(), SegTree[v].end(), x) – 
           SegTree[v].begin();

  int mid = (lpos + rpos) / 2;
  return Query(2*v, lpos, mid, left, min(mid, right), x) +
         Query(2*v+1, mid+1, rpos, max(left, mid+1), right, x);
}

C++

Parte principale del programma. Leggiamo l'array di numeri in ingresso.

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

Costruiamo l'albero dei segmenti a partire dall'array $a$ .

SegTree.resize(4*n);
build(1,1,n);

Elaboriamo in sequenza $q$ richieste.

scanf("%d",&q);
for(i = 0; i < q; i++)
{
  scanf("%d %d %d",&l,&r,&x);
  printf("%d\n",Query(1,1,n,l,r,x));
}