# Range trees

**URL:** <https://forum.olinfo.it/t/range-trees/3808>\
**Category:** Algoritmi\
**Created:** [17 Giugno 2014, 12:25pm UTC](https://forum.olinfo.it/t/range-trees/3808 "2014-06-17T12:25:36Z")\
**Posts on this page:** 11\
**Page:** 1

<div class="post-metadata">

**Author:** ![EmanueleRossi](https://forum.olinfo.it/user_avatar/forum.olinfo.it/emanuelerossi/32/42_2.png) [@EmanueleRossi](https://forum.olinfo.it/u/EmanueleRossi)\
**Post date:** [17 Giugno 2014, 12:25pm UTC](https://forum.olinfo.it/t/range-trees/3808/1 "2014-06-17T12:25:36Z")

</div>

Ciao, volevo chiedere se conoscete qualche referenza per i range trees, perchè nel sito ci sono alcuni problemi che ne richiedono l’utilizzo ma io non riesco a trovare nessun libro o risorsa in cui studiarli. Cercando sul web ho trovato praticamente solo wikipedia che ti dà una descrizione abbastanza generale ma poco pratica, e per esempio nel libro Introduction to algorithms e altri non se ne parla. Oppure è possibile che per caso siano conosciuti piu comunemente con un altro nome ed è per questo che non trovo niente? grazie in anticipo 🙂

---

<div class="post-metadata">

**Author:** ![Mazzetto](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/m/87869e/32.png) [@Mazzetto](https://forum.olinfo.it/u/Mazzetto)\
**Post date:** [17 Giugno 2014, 6:04pm UTC](https://forum.olinfo.it/t/range-trees/3808/2 "2014-06-17T18:04:24Z")

</div>

Generalmente per quanto riguarda i problemi, la struttura che si usa è quasi sempre il segment-tree. Su [topcoder](http://www.topcoder.com/tc?d1=tutorials&d2=lowestCommonAncestor&module=Static)&nbsp;c’è una guida carina sui segment tree. &nbsp;Applicazioni comuni dei segment tree sono il RSQ (Range Sum Query) e il RMQ (Range Minimum/Maximum Query), ma l’idea dietro il segment tree può essere estesa per risolvere molti altri problemi.

---

<div class="post-metadata">

**Author:** ![wil93](https://forum.olinfo.it/user_avatar/forum.olinfo.it/wil93/32/2862_2.png) [@wil93](https://forum.olinfo.it/u/wil93)\
**Post date:** [18 Giugno 2014, 12:55am UTC](https://forum.olinfo.it/t/range-trees/3808/3 "2014-06-18T00:55:06Z")

</div>

Aggiungo anche questa dispensa, scritta da Luca Wehrstedt, che è un ottimo ausilio alla lettura del tutorial postato da Mazzetto:

[rangetree-wehrstedt.pdf](https://forum.olinfo.it/uploads/default/original/1X/507ced3390e564083b3c2d9353dc802ff35098e8.pdf) (58,9 KB)

La sezione **1.3 Soluzione migliorata** corrisponde alla sezione **An \<O(N), O(sqrt(N))\> solution**

Le sezioni **1.4 Soluzione ottima** e **1.5 Implementazione** corrispondono alla sezione **Segment trees**

P.S.: attenzione alla confusione che si genera tra i termini _segment tree_, _range tree_, _interval tree_. Topcoder contribuisce alla confusione, chiamando segment tree ciò che andrebbe chiamato in realtà range tree.

---

<div class="post-metadata">

**Author:** ![EmanueleRossi](https://forum.olinfo.it/user_avatar/forum.olinfo.it/emanuelerossi/32/42_2.png) [@EmanueleRossi](https://forum.olinfo.it/u/EmanueleRossi)\
**Post date:** [18 Giugno 2014, 11:52pm UTC](https://forum.olinfo.it/t/range-trees/3808/4 "2014-06-18T23:52:15Z")

</div>

Grazie mille ragazzi, ho già un’infarinatura base dei segment trees perchè li avevo guardati su “Competitive Programming”, adesso anche grazie al materiale che mi avete dato li studio piu seriamente e almeno sapendo che si usano questi per le soluzioni dei cosiddetti “range trees” posso sperimentarli su un po di problemi concreti 🙂

---

<div class="post-metadata">

**Author:** ![EmanueleRossi](https://forum.olinfo.it/user_avatar/forum.olinfo.it/emanuelerossi/32/42_2.png) [@EmanueleRossi](https://forum.olinfo.it/u/EmanueleRossi)\
**Post date:** [19 Giugno 2014, 1:43pm UTC](https://forum.olinfo.it/t/range-trees/3808/5 "2014-06-19T13:43:02Z")

</div>

Ho provato il problema “Range tree 1”, quello delle monete testa o croce usando un segment tree. Solo che la mia idea supporta una query in lg N ma l’aggiornamento è lineare, infatti prendo i soliti 40 punti… Nel mio segment tree ho nella posizione che gestisce gli indici fra i,j (inclusi) le monete che mostrano testa in quell’intervallo. A questo punto una query che chiede le monete che mostrano testa può essere risolta facilmente in lg N , ma per aggiornare, devo aggiornare tutti gli intervalli che contengono anche solo un elemento che è stato capovolto, quindi tutte le posizioni che gesticono i,j con i=j che è un elemento aggiornato piu tutti i loro “genitori”…Idee migliori?

---

<div class="post-metadata">

**Author:** ![wil93](https://forum.olinfo.it/user_avatar/forum.olinfo.it/wil93/32/2862_2.png) [@wil93](https://forum.olinfo.it/u/wil93)\
**Post date:** [19 Giugno 2014, 2:05pm UTC](https://forum.olinfo.it/t/range-trees/3808/6 "2014-06-19T14:05:44Z")

</div>

È necessaria una tecnica nota come _lazy propagation_

---

<div class="post-metadata">

**Author:** ![EmanueleRossi](https://forum.olinfo.it/user_avatar/forum.olinfo.it/emanuelerossi/32/42_2.png) [@EmanueleRossi](https://forum.olinfo.it/u/EmanueleRossi)\
**Post date:** [19 Giugno 2014, 3:14pm UTC](https://forum.olinfo.it/t/range-trees/3808/7 "2014-06-19T15:14:25Z")

</div>

Thanks!!

---

<div class="post-metadata">

**Author:** ![EmanueleRossi](https://forum.olinfo.it/user_avatar/forum.olinfo.it/emanuelerossi/32/42_2.png) [@EmanueleRossi](https://forum.olinfo.it/u/EmanueleRossi)\
**Post date:** [20 Giugno 2014, 1:29pm UTC](https://forum.olinfo.it/t/range-trees/3808/8 "2014-06-20T13:29:03Z")

</div>

Guardandomi la lazy propagation sono riuscito a implementare questo ma continua a darmi execution timed out…

int update\_tree(int p, int L, int R, int i, int j) {

&nbsp; &nbsp;&nbsp;

if(L \> R || L \> j || R \< i) // Current segment is not within range [i, j]

return INF;

&nbsp; &nbsp;&nbsp;

&nbsp; if(L == R) { // Leaf node

&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;int d= 1-2_st[p];_

&nbsp; &nbsp; st[p] = 1 - st[p];

&nbsp; &nbsp; return d;

}

&nbsp;

int s = update\_tree(p2, L, (L+R)/2, i, j); // Updating left child

int s2 = update\_tree(1+p\*2, 1+(L+R)/2, R, i, j); // Updating right child

int d2 = ( (s!=INF ? s : 0) + (s2!=INF ? s2 : 0) );

st[p] += d2; // Updating root with max value

return d2;

}

  

  

In pratica arrivo alle foglie dentro l’intervallo, nelle quali scambio il valore( da 0 &nbsp;1 o viceversa, cioè da testa o croce o viceversa) e poi ritorno la differenza del loro valore ai genitori e cosi via fino alla radice, però bho mi sembra lineare con l’intervallo che vado a modificare, infatti è praticamente identica alla funzione che avevo utilizzato prima di guardare la lazy propagation, dov’è che toppo clamorosamente?🙂

---

<div class="post-metadata">

**Author:** ![EmanueleRossi](https://forum.olinfo.it/user_avatar/forum.olinfo.it/emanuelerossi/32/42_2.png) [@EmanueleRossi](https://forum.olinfo.it/u/EmanueleRossi)\
**Post date:** [20 Giugno 2014, 1:46pm UTC](https://forum.olinfo.it/t/range-trees/3808/9 "2014-06-20T13:46:45Z")

</div>

Ho trovato adesso il concetto di “Flag”… adesso ci do un’occhiata

---

<div class="post-metadata">

**Author:** ![wil93](https://forum.olinfo.it/user_avatar/forum.olinfo.it/wil93/32/2862_2.png) [@wil93](https://forum.olinfo.it/u/wil93)\
**Post date:** [21 Giugno 2014, 2:25pm UTC](https://forum.olinfo.it/t/range-trees/3808/10 "2014-06-21T14:25:43Z")

</div>

Sì, l’idea della lazy propagation è di tenere appunto un flag, o comunque un indicatore, che ti fa capire che in un certo nodo “è necessario applicare un’operazione all’intero intervallo che rappresenta”, però non lo fai subito… dato che la strategia è lazy = pigra.&nbsp;Quindi, quando un nodo ha l’indicatore lazy, tutti i discendenti hanno dei valori “outdated”, che non sono più corretti. Come si fa quindi quando ti si chiede un valore che però è “outdated”?

  

Semplicemente nella funzione di ricerca, man mano che scendi nell’albero, su tutti i nodi che incontri che hanno l’indicatore lazy effettui una _propagazione_&nbsp;dell’indicatore lazy ai due suoi figli _diretti_ (e non a tutti i discendenti), in questo modo da 1 indicatore lazy ora ne hai 2, però in compenso hai dei valori “outdated” in meno.

  

Quindi, riassumendo, esegui l’update solo “dove ti serve” e “man mano che ti serve”.

---

<div class="post-metadata">

**Author:** ![EmanueleRossi](https://forum.olinfo.it/user_avatar/forum.olinfo.it/emanuelerossi/32/42_2.png) [@EmanueleRossi](https://forum.olinfo.it/u/EmanueleRossi)\
**Post date:** [22 Giugno 2014, 9:34am UTC](https://forum.olinfo.it/t/range-trees/3808/11 "2014-06-22T09:34:55Z")

</div>

Si, ieri avevo letto un po sul web e sono riuscito a fare il problema 🙂 La chiave è appunto fare l’update effettivamente solo dove e quando ti serve e usare una flag per segnarti dove non è outdated!