Intervallo di intervallo con condizioni

Question

Supponiamo di avere un $ N $ Lunghezza Array intero di coppie del tipo $ [valore, chiave] $. Ora, devo interrogare per la somma della gamma. La query è del tipo: $ l, n, x $ Significa che devo riassumere tutto il $ valore $ Nell'intervallo indice $ l $ a $ N $ avere la chiave come $ x $. Inoltre, ci possono essere aggiornamenti che aggiungono una nuova coppia alla fine dell'array in aumento $ N $. Le domande successive considerano l'aggiornamento $ N $. Ci possono essere più domande, quindi devo rispondere alla query $ O (logn) $ Ma è consentita la precomputazione.

Penso che potrebbe essere fatto con un albero di segmenti ma non riesco a vedere cosa tenere nei nodi. È anche possibile farlo con la complessità richiesta, perché sento che devi effettivamente andare ad ogni elemento dell'array per verificare la chiave. Qualsiasi aiuto è apprezzato.