Հատվածի գումարների հարցումներ 2
Ձեզ տրված է
n տարրերից կազմված զանգված և q հարցումներ: Հարցումները երկու տեսակ են.- Հաշվել տրված հատվածի տարրերի գումարը
- Թարմացնել զանգվածի տարրի արժեքը տվյալ դիրքում
Ձեր խնդիրն է արդյունավետորեն մշակել բոլոր հարցումները:
Մուտք
Մուտքի առաջին տողում տրված են երկու ամբողջ թիվ
n և q (1 ≤ n, q ≤ 100000), որոնք համապատասխանաբար ցույց են տալիս զանգվածի տարրերի քանակն ու հարցումների քանակը:Մուտքի երկրորդ տողում տրված են
n ամբողջ թվեր ( ), որոնք սահմանում են զանգվածի նախնական տարրերը:Հաջորդ
q տողերից յուրաքանչյուրն արտացոլում է մեկ հարցում.- Եթե հարցումը հատվածի գումարի մասին է, ապա տողը սկսվում է թիվ
1-ով, որին հաջորդում են երկու ամբողջ թվեր և ( ), որոնք նշում են[ $$l_i, r_i$$ ]միջակայքը, որի տարրերի գումարը պետք է հաշվել:
- Если հարցումը զանգվածի թարմացման մասին է, ապա տողը սկսվում է թիվ
2-ով, որին հետեւում են երկու ամբողջ թվեր և ( 1 ≤ pi ≤ n, -10^9 ≤ xi ≤ 10^9 ), որոնք համապատասխանաբար սահմանում են թարմացվող տարրի ինդեքսը () և դրա նոր արժեքը ():
Ելք
Յուրաքանչյուր հատվածի գումարի հարցման համար պետք է տպել տվյալ հատվածի տարրերի գումարը առանձին տողով:
Օրինակներ
Մուտք | Ելք |
5 3
1 2 3 4 5
1 1 3
1 2 4
1 1 5 | 6
9
15 |
5 3
1 2 3 4 5
1 1 3
2 1 5
1 1 5 | 6
19 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB