Laiko ribojimas: 1s

Atminties ribojimas: 1024MB

Duomenų failas: segment_tree.in

Rezultatų failas: segment_tree.out

Jei norite pateikti savo sprendimą - prisijunkite.

Masyvo užklausos

Jūs turite masyvą, sudarytą iš n sveikųjų skaičių a_1, a_2, a_3, ..., a_n. Jūsų uždavinys - įvykdyti q užklausų turimam skaičių sekai.

Užklausos gali būti dviejų tipų:

  1. Sumos užklausa: apskaičiuoti visų į intervalą [l,r] įeinančių elementų sumą.
  2. Pridėjimo užklausa: Prie sekos elemento esančio indekse l pridėti skaičių r.

Pradiniai duomenys

Pirmoje eilutėje pateikti du skaičiai n (1\\leqn\\leq100000) ir q (1\\leqq\\leq100000) atitinkamai nurodantys masyvo elementų skaičių bei užklausų kiekį.

Antroje eilutėje pateikta n masyvo skaičių 0\\leqa_1,a_2,a_3,...,a_n\\leq100000.

Kitose kiekvienoje q eilučių pateikti užklausų duomenys c - užklausos tipą, 0\\leql\\leq100000, bei 0\\leqr\\leq100000. Jei c_i=?, tai turi būti atliekama sumos užklausa, jei c_i=+, tai turi būti atliekama pridėjimo užklausa.

Pastaba: masyvo indeksai skaičiuojami nuo 0.

Rezultatai

Kiekvienai sumos tipo užklausai išvesti užklausos rezultatą.

Pavyzdžiai

Pradiniai duomenys Rezultatai 
5 5
1 2 1 2 2 
+ 2 2
+ 3 4
? 2 4
? 1 2
+ 2 1
 
11
5