Solutie prototip: (nonfinala)
Problema este o aplicatie clasica a arborilor de intervale cu lazy propagation. Fiecare nod al arborelui de intervale va retine informatii legate de:

* Capatul stang al intervalului (st)
* Capatul drept al intervalului (dr)
* Suma elementelor din interval (s1)
* Raspunsul la un query fix pe acel interval (s2)
Acum singura problema care ne mai ramane este unirea a doua noduri a si b intr-un singur nod c (altfel spus, unirea a doua jumatati de interval intr-un singur interval, mentinand toate informatiile de mai sus). Informatiile legate de capetele noului interval sunt usor de calculat dupa urmatoarele formule intuitive:

== code(cpp) |
a.st = b.st;
a.dr = c.dr;
==

Calcularea sumei noului interval se obtine prin adunarea sumelor intervalelor a si b.

== code(cpp) |
a.s1 = b.s1 + c.s1;
==

Calcularea noului s2 este putin mai complexa:

== code(cpp) |
a.s2 = b.s2 + (c.s2 + c.s1 * (b.dr - b.st + 1) );
==