Ավելի արագ միջակայքային հարցումներ
Տրված է
n ամբողջ թիվ ունեցող a զանգվածը, որի վրա պետք է պատասխանել q հարցումների։ Այս բոլոր հարցումներն ունեն հետևյալ տեսքը․ «Գումարել a զանգվածի [l; r] ինդեքսներում գտնվող բոլոր տարրերը» (երբ երկու ծայրակետերն էլ ներառյալ են, իսկ ինդեքսավորումը սկսվում է 0-ից)։ Այս անգամ թե՛ զանգվածի չափը, թե՛ հարցումների քանակը զգալիորեն ավելի մեծ են։ Կկարողանա՞ք մտածել, թե ինչպես ավելի արագ պատասխանել այդ հարցումներին։Մուտք
Մուտքի առաջին տողում տրված է մեկ ամբողջ թիվ
n — զանգվածի տարրերի քանակը (1 ≤ n ≤ )։Հաջորդ տողում տրված են
n ամբողջ թվեր, որոնք կազմում են զանգվածը ։Ելք
Ծրագիրը պետք է տպի
q տող, որոնցից յուրաքանչյուրում պետք է արտածել a զանգվածի [l_j, r_j] միջակայքի տարրերի գումարը (ներառյալ ծայրակետերը)։Օրինակներ
Մուտք | Ելք |
8
1 2 3 4 5 6 7 8
3
0 4
5 6
5 7 | 15
13
21 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 25 MB