Հատվածի գումարների հարցումներ
Ձեզ խնդրում են գրել ծրագիր, որը ստանալով
n էլեմենտներից կազմված զանգված եւ q հատ հատվածի գումարների հարցում, պետք է արդյունավետորեն պատասխանել յուրաքանչյուր հարցման: Դրա համար անհրաժեշտ է հաշվել տվյալ հատվածի էլեմենտների գումարը, օգտագործելով Հատվածներով ծառ (Segment Tree) տվյալ կառուցվածքը:Մուտք
Մուտքի առաջին տողում տրված են երկու ամբողջ թվեր
n եւ q (1 ≤ n, q ≤ 100000), որոնք ցույց են տալիս զանգվածի էլեմենտների քանակը եւ հարցումների քանակը, համապատասխանաբար:Երկրորդ տողում տրված են
n ամբողջ թվեր (), որոնք ներկայացնում են զանգվածի էլեմենտները:Հաջորդ
q տողերից յուրաքանչյուրում տրված են երկու ամբողջ 숫եր եւ (), որոնք սահմանում են համապատասխան հարցման համար հաշվվող հատվածը:Ելք
Յուրաքանչյուր հարցման համար առանձին տողում տպեք տվյալ հատվածում գտնվող բոլոր էլեմենտների գումարը:
Օրինակներ
Մուտք | Ելք |
5 3
1 2 3 4 5
1 3
2 4
1 5 | 6
9
15 |
Բացատրություն
Տրված
[1, 2, 3, 4, 5] զանգվածի համար իրականացնում ենք հետեւյալ հատվածի գումարների հարցումները.- Հարցում
[1, 3]: [1, 3] հատվածի էլեմենտների գումարը հավասար է 1 + 2 + 3 = 6.
- Հարցում
[2, 4]: [2, 4] հատվածի էլեմենտների գումարը հավասար է 2 + 3 + 4 = 9.
- Հարցում
[1, 5]: [1, 5] հատվածի էլեմենտների գումարը հավասար է 1 + 2 + 3 + 4 + 5 = 15.
Constraints
Time limit: 10 seconds
Memory limit: 512 MB
Output limit: 1 MB