Prefiks yig‘indilar

Prefiks yig‘indi: p[i] = a[0] + ... + a[i-1]. Shunda [l, r] oraliq yig‘indisi bir amalda:

p = [0]
for x in a:
    p.append(p[-1] + x)
# a[l..r] (0 dan, ikkala chegara kiradi):
s = p[r + 1] - p[l]

Q ta so‘rovda har birini sikl bilan hisoblash O(n·q), prefiks bilan — O(n + q).

Kengaytmalar: ikki o‘lchovli prefiks (to‘g‘ri to‘rtburchak yig‘indisi), farq massivi (oraliqqa qo‘shish).