Requête de gamme avec conditions

Question

Supposons que j'ai un $ N $ Tableau entier de longueur de paires du type $ [valeur, clé] $. Maintenant, je dois interroger pour la somme de la gamme. La requête est du type: $ l, n, x $ ce qui signifie que je dois résumer tous les $ valeur $ dans la plage d'index $ l $ à $ N $ avoir la clé que $ x $. De plus, il peut y avoir des mises à jour qui ajoutent une nouvelle paire à la fin de l'augmentation du tableau $ N $. Les requêtes successives considèrent la mise à jour $ N $. Il peut y avoir plusieurs requêtes, j'ai donc besoin de répondre à la requête en $ O (logn) $ Mais la précomputation est autorisée.

Je pense que cela pourrait être fait avec un arbre de segment mais je ne vois pas quoi garder dans les nœuds. Est-il même possible de le faire avec la complexité requise, car je pense que vous devez réellement aller à chaque élément du tableau pour vérifier sa clé. Toute aide est appréciée.