Module: Décomposition des racines


Problem

3 /6


Somme sur segment - 2

Theory Click to read/hide

Nous avons un problème sur la façon de calculer rapidement les sommes sur l'intervalle l...r dans le tableau a, dans lequel les éléments peuvent changer un à la fois, en asymptotique inférieure à O(n).
Cette tâche est résolue de la même manière que la précédente, mais lors d'une demande de modification, vous devez modifier le montant dans le bloc correspondant.

Problem

Étant donné un tableau a de longueur n (\(1 <= n <= 2 \cdot 10^6\ )< /span>, \(1 <= a_i <= 10^9\)). Donne également des requêtes m (\(1 <= m <= 500\)) comme t, l, r (\(0 <= t <= 1\), \(1 <= l <= r <= n\)).

Si \(t = 0\), alors la requête doit afficher la somme des nombres dans le segment à partir de l à r inclus. Si \(t = 1\), alors le numéro d'élément l est défini sur r. Les éléments sont numéroté de 1 à n. 

 

Exemples
5
1 2 3 4 5
4
0 1 2
1 1 5
0 1 2
0 1 1
# Entrée Sortie
1 3
7
5

time 3000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!