Oraliq yig'indisi

$n$ ta butun sondan iborat massiv va $q$ ta so'rov berilgan. Har bir so'rovda $a_l + a_{l+1} + \ldots + a_r$ yig'indini toping.

Birinchi qatorda $n$ va $q$ ($1 \le n, q \le 2 \cdot 10^5$). Ikkinchi qatorda $n$ ta butun son ($|a_i| \le 10^9$). Keyingi $q$ ta qatorning har birida so'rov: ikkita butun son $l$ va $r$ ($1 \le l \le r \le n$).

Har bir so'rov uchun alohida qatorda bitta son — yig'indi.

Har bir so'rovda sikl bilan qo'shish $O(nq)$ — $4 \cdot 10^{10}$ amal. Prefiks yig'indi $p_i = a_1 + \ldots + a_i$ ($p_0 = 0$) ni bir marta hisoblang, keyin har bir javob $p_r - p_{l-1}$ — $O(1)$.

Yig'indi $2 \cdot 10^{14}$ gacha yetadi — 64 bitli tur kerak.

Manba: CSES, 1646-masala.