Sto cercando di risolvere il terzo problema sui rangetree Can you answer these queries III ( rangetree3 ), e la seconda operazione richiesta dal problema non mi è chiara.
Pensavo che richiedesse la somma massima nel range dato in input, ma nella seconda query dopo la modifica restitusice 4.
Altro disegnigno brutto sempre fatto da me ^-^
Ciao, la seconda operazione richiede la massima somma di valori adiacenti all’interno dell’intervallo.
Nel caso dell’operazione q(2,4) le possibili somme sono:
In questo caso la somma massima è 4. Non si può ottenere la somma di 2 e 4 perché i due valori non sono adiacenti.
Questo è lo stesso problema (senza la parte degli update): https://en.wikipedia.org/wiki/Maximum_subarray_problem
Grazie mille della spiegazione, ora provo a risolverlo.
Tra l’altro sarebbe carino diminuire i limiti di tempo / sistemare gli input perché è possibile prendere 100 punti con una soluzione O(NM) 
