Laiko ribojimas: 1s

Atminties ribojimas: 256MB

Duomenų failas: segment_tree_3.in

Rezultatų failas: segment_tree_3.out

Jei norite pateikti savo sprendimą - prisijunkite.

Masyvo užklausos 3

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ų turimai skaičių sekai.

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

  1. Sumos užklausa: apskaičiuoti elementų a_l,a_{l+1},...a_r sumą.
  2. Pridėjimo užklausa: prie sekos elementų a_l,a_{l+1},...a_r pridėti skaičių d.

Pradiniai duomenys

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

Antroje eilutėje pateikta n skaičių a_i: pradinės elementų reikšmės. 0\\leqa_1,a_2,a_3,...,a_n\\leq200000.

Kitose q eilučių pateikti užklausų duomenys: Simbolis c - užklausos tipas (? arba +). Jei c yra ?, tai toje eilutėje taip pat yra du skaičiai l ir r - sumuojamo intervalo pradžia ir pabaiga (1\\leql\\leqr\\leqn). Jei c yra +, tai toje eilutėje toliau yra trys skaičiai: l,r,d - pridėjimo užklausos intervalo pradžia, pabaiga, ir prie elementų pridedama reikšmė (1\\leql\\leqr\\leqn,0\\leqd\\leq200000).

Rezultatai

Kiekvienai ? tipo užklausai išveskite prašomų elementų sumą.

Pavyzdžiai

Pradiniai duomenys Rezultatai 
5 6
5 5 3 4 0
+ 1 4 5
+ 3 5 5
? 2 4
+ 1 2 0
+ 3 5 1
? 3 5
 
37
35
 
2 7
3 2
? 1 1
? 2 2
? 1 2
+ 1 2 4
? 1 1
? 2 2
? 1 2
 
3
2
5
7
6
13