Dima e l'array#2941

Dima e l'array (Editoriale)

Il problema richiede di elaborare operazioni di due tipi:

assegnare un valore a un elemento dell'array;
calcolare la somma degli elementi sul segmento $[f; t]$ .

Abbiamo bisogno di una struttura dati che esegua entrambe le operazioni velocemente. Una struttura di questo tipo è un segment tree per le somme. Ciascuno dei suoi vertici memorizza la somma degli elementi del proprio segmento, e il valore in un vertice interno è uguale alla somma dei valori dei suoi due figli.

Il segment tree permette sia di calcolare la somma su un segmento sia di modificare un elemento dell'array in $O (lo g n)$ O(\log n).

Esempio

Simuliamo le query dell'esempio. Inizialmente, l'array è $(1, 2, 3)$ (1, 2, 3).

$? 13$ : la somma degli elementi sul segmento $[1; 3]$ è $1 + 2 + 3 = 6$ 1 + 2 + 3 = 6;
$= 32$ : all'elemento $a_{3}$ a_3 viene assegnato il valore $2$ , e l'array diventa $(1, 2, 2)$ (1, 2, 2);
$? 13$ : la somma degli elementi sul segmento $[1; 3]$ è $1 + 2 + 2 = 5$ 1 + 2 + 2 = 5.

Vediamo come cambia il segment tree. La figura a sinistra mostra l'albero per l'array iniziale, e la figura a destra lo mostra dopo l'assegnazione $a_{3} = 2$ a_3 = 2. Ogni vertice mostra il proprio segmento e la somma degli elementi su di esso; i vertici modificati sono evidenziati.

Il segmento $[1; 3]$ di entrambe le query coincide con il segmento della radice, quindi la risposta viene presa direttamente dalla radice: $6$ prima dell'assegnazione e $5$ dopo di essa. Durante l'assegnazione $a_{3} = 2$ a_3 = 2, vengono ricalcolati solo i vertici sul percorso dalla foglia $[3]$ alla radice: la foglia $[3]$ riceve il valore $2$ , e la radice riceve il valore $3 + 2 = 5$ 3 + 2 = 5.

Implementazione dell'algoritmo

Memorizziamo il segment tree nel vettore $S e g T r ee$ SegTree di lunghezza $4 \cdot M A X$ 4 \cdot MAX, dove $M A X = 5 \cdot 1 0^{5}$ MAX = 5 \cdot 10^5 è il numero massimo di elementi dell'array. Ogni vertice dell'albero memorizza la somma degli elementi del proprio segmento.

#define MAX 500000
vector<int> SegTree(4*MAX,0);

La funzione BuildTree costruisce il segment tree a partire dall'array $a$ . Riceve il numero del vertice corrente $v$ e gli estremi $l p os$ e $r p os$ del segmento corrispondente a questo vertice.

void BuildTree(vector<int>&a, int v, int lpos, int rpos)
{

Se il segmento del vertice $v$ è costituito da un solo elemento ( $l p os = r p os$ lpos = rpos), allora $v$ è una foglia dell'albero. Scriviamo in esso il valore $a [l p os]$ .

  if (lpos == rpos) SegTree[v] = a[lpos];
  else
  {

Altrimenti, troviamo il punto medio del segmento $mi d = (l p os + r p os) /2$ mid = (lpos + rpos) / 2.

    int mid = (lpos + rpos) / 2;

Il segmento $[l p os; r p os]$ [lpos; rpos] viene suddiviso in due sottosegmenti $[l p os; mi d]$ [lpos; mid] e $[mi d + 1; r p os]$ [mid + 1; rpos]. Costruiamo ricorsivamente l'albero per il figlio sinistro $2 v$ e il figlio destro $2 v + 1$ 2v + 1.

    BuildTree(a, 2*v, lpos, mid);
    BuildTree(a, 2*v+1, mid + 1, rpos);

Il valore nel vertice $v$ è uguale alla somma dei valori dei suoi figli.

    SegTree[v] = SegTree[2*v] + SegTree[2*v+1];
  }
}

La funzione Update assegna il valore $v a l$ all'elemento con indice $p os$ . Il vertice $v$ corrisponde al segmento $[l p os; r p os]$ [lpos; rpos].

void Update(int v, int lpos, int rpos, int pos, int val)
{

Se il vertice $v$ è una foglia ( $l p os = r p os$ lpos = rpos), esso corrisponde alla posizione $p os$ . Scriviamo in esso il valore $v a l$ .

  if (lpos == rpos) SegTree[v] = val;
  else
  {

Altrimenti, determiniamo quale metà del segmento contiene la posizione $p os$ , e scendiamo ricorsivamente nel figlio sinistro o destro.

    int mid = (lpos + rpos) / 2;
    if (pos <= mid)
      Update (2*v, lpos, mid, pos, val);
    else
      Update (2*v+1, mid+1, rpos, pos, val);

Dopo essere tornati dalla ricorsione, ricalcoliamo la somma nel vertice $v$ . In questo modo, vengono aggiornati tutti i vertici sul percorso dalla foglia alla radice.

    SegTree[v] = SegTree[2*v] + SegTree[2*v+1];
  }
}

La funzione Summa restituisce la somma degli elementi sul segmento $[l e f t; r i g h t]$ [left; right]. Il vertice $v$ corrisponde al segmento $[l p os; r p os]$ [lpos; rpos]. Se il segmento di query è vuoto ( $l e f t > r i g h t$ left > right), restituiamo $0$ — l'elemento neutro per l'addizione.

int Summa(int v, int lpos, int rpos, int left, int right)
{
  if (left > right) return 0;

Se il segmento di query coincide con il segmento del vertice, la risposta è memorizzata in $S e g T r ee [v]$ SegTree[v].

  if ((left == lpos) && (right == rpos))
    return SegTree[v];

Altrimenti, troviamo il punto medio del segmento $mi d = (l p os + r p os) /2$ mid = (lpos + rpos) / 2.

  int mid = (lpos + rpos) / 2;

Suddividiamo il segmento di query in due parti: $[l e f t; min (r i g h t, mi d)]$ [left; \min(right, mid)] si trova nel segmento del figlio sinistro, e $[max (l e f t, mi d + 1); r i g h t]$ [\max(left, mid + 1); right] si trova nel segmento del figlio destro. Una delle parti può essere vuota. Restituiamo la somma dei risultati per entrambi i figli.

  return Summa(2*v, lpos, mid, left, min(right,mid)) +
         Summa(2*v+1, mid+1, rpos, max(left,mid+1), right);
}

La parte principale del programma. Leggiamo la dimensione dell'array $n$ , il numero di query $q$ , e gli elementi dell'array nel vettore $v$ , a partire dall'indice $1$ . La chiamata scanf("\n") salta il ritorno a capo dopo l'array, in modo che il carattere successivo letto sia il segno dell'operazione.

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

Costruiamo il segment tree a partire dagli elementi $v [1 \dots n]$ v[1 \ldots n].

BuildTree(v,1,1,n);

Elaboriamo le $q$ query una per una. Per prima cosa, leggiamo il carattere dell'operazione $c$ ; lo spazio nel formato "%c " salta lo spazio dopo di esso. Se $c$ = '=', assegniamo il valore $d$ all'elemento con indice $i$ . Altrimenti, calcoliamo e stampiamo la somma sul segmento $[f; t]$ . Il carattere \n nel formato "%d %d\n" salta il ritorno a capo, in modo che la lettura successiva in $c$ ottenga il segno dell'operazione successiva.

for(j = 0; j < q; j++)
{
  scanf("%c ",&c);
  if (c == '=')
  {
    scanf("%d %d\n",&i,&d);
    Update(1,1,n,i,d);
  } else
  {
    scanf("%d %d\n",&f,&t);
    printf("%d\n",Summa(1,1,n,f,t));
  }
}

C++