Somma su un segmento (Editoriale)

Il problema richiede l'elaborazione di query di due tipi: assegnare un valore a un elemento dell'array e calcolare la somma degli elementi sul segmento $[l; r]$ [l; r]. Se memorizziamo solo l'array stesso, un'assegnazione richiede $O (1)$ , ma ogni query di somma richiede $O (n)$ operazioni. Se memorizziamo le somme prefisse, una somma viene calcolata in $O (1)$ , ma ogni assegnazione richiede di ricalcolare $O (n)$ somme prefisse. Con un numero elevato di query, entrambi gli approcci sono troppo lenti.

Utilizziamo un albero dei segmenti 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. L'albero dei segmenti esegue entrambe le operazioni in $O (lo g n)$ O(\log n). Nel calcolo di una somma, una parte vuota di un segmento corrisponde a $0$ — l'elemento neutro per l'addizione.

Inizialmente tutti gli elementi dell'array sono zero, quindi anche le somme in tutti i vertici dell'albero sono zero. È sufficiente riempire l'array dell'albero con zeri; non è necessaria una costruzione separata dell'albero.

I valori degli elementi raggiungono $1 0^{9}$ 10^9, quindi la somma su un segmento può raggiungere $1 0^{5} \cdot 1 0^{9} = 1 0^{14}$ 10^5 \cdot 10^9 = 10^{14} e non entra nel tipo int. I valori nell'albero sono memorizzati nel tipo long long.

Consideriamo una soluzione che utilizza un albero di Fenwick. Esso supporta due operazioni, ciascuna eseguita in $O (lo g n)$ O(\log n):

aggiungere un numero $d e l t a$ all'elemento $a_{i}$ a_i;
calcolare la somma prefissa $s u m (i) = a_{0} + a_{1} + \dots + a_{i}$ sum(i) = a_0 + a_1 + \ldots + a_i.

Inizialmente tutti gli elementi dell'array sono zero, quindi un albero di Fenwick riempito con zeri corrisponde già all'array iniziale. Gli indici nelle query vanno da $1$ a $n$ ; l'elemento $a_{0}$ a_0 non è utilizzato ed è sempre zero.

Assegnazione. Un albero di Fenwick può solo aggiungere un numero a un elemento, ma non può assegnargli un nuovo valore. Tuttavia, il valore corrente di un elemento può essere calcolato tramite le somme prefisse:

a_{i} = s u m (i) - s u m (i - 1)

a_i = sum(i) - sum(i - 1)

Pertanto, l'assegnazione $a_{i} = x$ a_i = x viene sostituita aggiungendo ad $a_{i}$ a_i la differenza tra il nuovo e il vecchio valore:

d e l t a = x - (s u m (i) - s u m (i - 1)) = x - s u m (i) + s u m (i - 1)

delta = x - (sum(i) - sum(i - 1)) = x - sum(i) + sum(i - 1)

Somma su un segmento. La somma degli elementi sul segmento $[l; r]$ [l; r] è uguale alla differenza di due somme prefisse:

a_{l} + a_{l + 1} + \dots + a_{r} = s u m (r) - s u m (l - 1)

a_l + a_{l+1} + \ldots + a_r = sum(r) - sum(l - 1)

I valori degli elementi raggiungono $1 0^{9}$ 10^9, quindi le somme possono raggiungere $1 0^{14}$ 10^{14} e sono memorizzate nel tipo long long.

Esempio

Inizialmente l'array è composto da zeri. Dopo le query $A 22$ , $A 31$ e $A 42$ , l'array diventa $(0, 2, 1, 2, 0)$ (0, 2, 1, 2, 0). L'albero dei segmenti per esso è mostrato di seguito. Ogni vertice mostra il proprio segmento e la somma degli elementi su di esso.

Quando viene eseguita la query $A 31$ , vengono ricalcolati solo i vertici sul percorso dalla foglia $[3]$ alla radice: la foglia $[3]$ riceve il valore $1$ , il vertice $[1; 3]$ — il valore $2 + 1 = 3$ 2 + 1 = 3, e la radice $[1; 5]$ — il valore $3 + 2 = 5$ 3 + 2 = 5.

Le query $Q 11$ , $Q 22$ , $Q 33$ , $Q 44$ e $Q 55$ restituiscono i valori delle foglie: $0, 2, 1, 2, 0$ 0, 2, 1, 2, 0. Il segmento della query $Q 15$ coincide con il segmento della radice, quindi la risposta è presa direttamente dalla radice ed è uguale a $5$ (il vertice evidenziato).

Simuliamo le query dell'esempio utilizzando l'albero di Fenwick, $n = 5$ n = 5. Inizialmente l'array è $(0, 0, 0, 0, 0)$ (0, 0, 0, 0, 0). Per ogni query di assegnazione, la tabella mostra come viene calcolato il vecchio valore dell'elemento e quale numero viene aggiunto; per ogni query di somma, mostra la differenza delle somme prefisse.

query	calcolo	risultato
$A 22$	vecchio valore $s u m (2) - s u m (1) = 0 - 0 = 0$ sum(2) - sum(1) = 0 - 0 = 0, aggiunto $2 - 0 = 2$ 2 - 0 = 2	$(0, 2, 0, 0, 0)$ (0, 2, 0, 0, 0)
$A 31$	vecchio valore $s u m (3) - s u m (2) = 2 - 2 = 0$ sum(3) - sum(2) = 2 - 2 = 0, aggiunto $1 - 0 = 1$ 1 - 0 = 1	$(0, 2, 1, 0, 0)$ (0, 2, 1, 0, 0)
$A 42$	vecchio valore $s u m (4) - s u m (3) = 3 - 3 = 0$ sum(4) - sum(3) = 3 - 3 = 0, aggiunto $2 - 0 = 2$ 2 - 0 = 2	$(0, 2, 1, 2, 0)$ (0, 2, 1, 2, 0)
$Q 11$	$s u m (1) - s u m (0) = 0 - 0$ sum(1) - sum(0) = 0 - 0	$0$
$Q 22$	$s u m (2) - s u m (1) = 2 - 0$ sum(2) - sum(1) = 2 - 0	$2$
$Q 33$	$s u m (3) - s u m (2) = 3 - 2$ sum(3) - sum(2) = 3 - 2	$1$
$Q 44$	$s u m (4) - s u m (3) = 5 - 3$ sum(4) - sum(3) = 5 - 3	$2$
$Q 55$	$s u m (5) - s u m (4) = 5 - 5$ sum(5) - sum(4) = 5 - 5	$0$
$Q 15$	$s u m (5) - s u m (0) = 5 - 0$ sum(5) - sum(0) = 5 - 0	$5$

Ad esempio, prima della query $Q 44$ l'array è $(0, 2, 1, 2, 0)$ (0, 2, 1, 2, 0), quindi $s u m (4) = 0 + 2 + 1 + 2 = 5$ sum(4) = 0 + 2 + 1 + 2 = 5, $s u m (3) = 0 + 2 + 1 = 3$ sum(3) = 0 + 2 + 1 = 3, e la risposta è $5 - 3 = 2$ 5 - 3 = 2.

Nell'esempio, tutte le assegnazioni vengono applicate a elementi nulli. Vediamo cosa accadrebbe con un'assegnazione ripetuta, ad esempio $A 35$ alla fine. Il vecchio valore è $s u m (3) - s u m (2) = 3 - 2 = 1$ sum(3) - sum(2) = 3 - 2 = 1, quindi $5 - 1 = 4$ 5 - 1 = 4 viene aggiunto ad $a_{3}$ a_3, e l'elemento diventa $5$ .

Implementazione dell'algoritmo

L'albero dei segmenti è memorizzato nell'array $S e g T r ee$ SegTree di lunghezza $4 \cdot M A X$ 4 \cdot MAX, dove $M A X$ è il numero massimo di elementi dell'array. Una somma su un segmento può superare i limiti del tipo int, quindi i valori nell'albero hanno il tipo long long.

#define MAX 100010
long long SegTree[4 * MAX];

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

long long Summa(int v, int lpos, int rpos, int left, int right)
{

Se il segmento della query è vuoto ( $l e f t > r i g h t$ left > right), restituire $0$ — l'elemento neutro per l'addizione.

  if (left > right) return 0;

Se il segmento della query coincide con il segmento $[l p os; r p os]$ [lpos; rpos] del vertice $v$ , restituire la somma memorizzata in esso.

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

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

  int mid = (lpos + rpos) / 2;

Suddividere il segmento della 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. Calcolare ricorsivamente le somme su entrambe le parti e restituire la loro somma.

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

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 segmento del vertice $v$ è composto da un solo elemento ( $l p os = r p os$ lpos = rpos), allora $v$ è la foglia corrispondente alla posizione $p os$ . Scrivere in essa il valore $v a l$ .

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

Altrimenti, determinare quale metà del segmento contiene la posizione $p os$ , e discendere 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 il ritorno dalla ricorsione, ricalcolare 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 parte principale del programma. Inizialmente tutti gli elementi dell'array sono zero, quindi anche tutte le somme nell'albero dei segmenti sono zero. Riempire l'array $S e g T r ee$ SegTree con zeri; non è necessaria una costruzione separata dell'albero.

memset(SegTree, 0, sizeof(SegTree));

Leggere la dimensione dell'array $n$ e il numero di query $k$ . Il carattere \n nel formato salta l'interruzione di riga, in modo che il carattere successivo letto sia la lettera della query.

scanf("%d %d\n", &n, &k);

Elaborare le $k$ query una per una. Prima, leggere la lettera della query $co mman d$ . Se è 'A', assegnare il valore $x$ all'elemento con indice $i$ . Altrimenti, stampare la somma sul segmento $[l; r]$ [l; r]. Il carattere \n nel formato "%lld %lld\n" salta l'interruzione di riga dopo la query.

for (j = 0; j < k; j++)
{
  scanf("%c", &command);
  if (command == 'A')
  {
    scanf("%lld %lld\n", &i, &x);
    update(1, 1, n, i, x);
  }
  else
  {
    scanf("%lld %lld\n", &l, &r);
    printf("%lld\n", Summa(1, 1, n, l, r));
  }
}

C++

Implementazione dell'algoritmo — albero di Fenwick

L'array $F e n w i c k$ Fenwick di dimensione $M A X$ memorizza l'albero di Fenwick. Un array globale è inizialmente riempito con zeri, il che corrisponde all'array iniziale nullo.

#define MAX 100010
long long Fenwick[MAX];

La funzione Summma0_i restituisce la somma prefissa $s u m (i) = a_{0} + a_{1} + \dots + a_{i}$ sum(i) = a_0 + a_1 + \ldots + a_i.

// Fenwick[0] + Fenwick[1] + ... + Fenwick[i]
long long Summma0_i(long long i)
{
  long long result = 0;
  for (; i >= 0; i = (i & (i + 1)) - 1)
    result += Fenwick[i];
  return result;
}

C++

La funzione IncElement aggiunge $d e l t a$ all'elemento $a_{i}$ a_i. Gli indici degli elementi vanno da $1$ a $n$ , quindi il ciclo viene eseguito finché $i \leq n$ i \le n.

// Fenwick[i] = Fenwick[i] + delta
void IncElement(long long i, long long delta)
{
  for (; i <= n; i = (i | (i+1)))
    Fenwick[i] += delta;
}

La parte principale del programma. Leggere la dimensione dell'array $n$ e il numero di query $k$ . Il carattere \n nel formato salta l'interruzione di riga, in modo che il carattere successivo letto sia la lettera della query.

scanf("%d %d\n",&n,&k);

Elaborare le $k$ query una per una. Prima, leggere la lettera della query $co mman d$ .

for(j = 0; j < k; j++)
{
  scanf("%c",&command);

Query $A i x$ . Il valore corrente dell'elemento $a_{i}$ a_i è uguale a $s u m (i) - s u m (i - 1)$ sum(i) - sum(i - 1). Per assegnargli il valore $x$ , si sostituisce $x$ con la differenza $x - s u m (i) + s u m (i - 1)$ x - sum(i) + sum(i - 1) e la si aggiunge ad $a_{i}$ a_i utilizzando la funzione IncElement.

  if (command == 'A')
  {
    scanf("%lld %lld\n",&i,&x);
    x = x - Summma0_i(i) + Summma0_i(i-1);
    IncElement(i,x);

Query $Q l r$ . La somma sul segmento $[l; r]$ [l; r] è uguale a $s u m (r) - s u m (l - 1)$ sum(r) - sum(l - 1).

  } else
  {
    scanf("%lld %lld\n",&l,&r);
    printf("%lld\n",Summma0_i(r) - Summma0_i(l-1));
  }
}