Zbroj dijela
Zadana je lista od N brojeva i Q pitanja. Za svako pitanje l, r ispiši zbroj elemenata od l-tog do r-tog (elementi su numerirani od 1).
- Ulaz
U prvom retku N, u drugom N brojeva. U trećem retku Q, zatim Q redaka s brojevima l i r.
- Izlaz
Q redaka s odgovorima.
- Ograničenja
1 ≤ N, Q ≤ 100 000, 1 ≤ l ≤ r ≤ N, brojevi su od −1000 do 1000
Primjer 1
Ulaz
6 3 1 4 1 5 9 3 3 5 1 6 2 2
Izlaz
10 23 1
Zapeo si?
Prvo pokušaj sam. Savjeti se otvaraju jedan po jedan, svaki otkriva malo više.
Napravi prefiksne zbrojeve jednom, na početku.
Kako iz dva prefiksna zbroja dobiti zbroj dijela u sredini? Probaj na papiru.