Asosiy qismga o‘tish
Orqaga Mutaxassislik fan Informatika · SamDU 2-sonli akademik litseyi
Tizimga kirish

6. Prefiks yig‘indi

Nazariya

Muammo

q ta so‘rov: har birida l dan r gacha yig‘indi. Har safar
sanasak O(n·q) — 200 000 × 200 000 ulgurmaydi.

Yechim

Bir marta prefiks yig‘indilar massivini quramiz: p[i] — birinchi i
ta elementning yig‘indisi.

p = [0] * (n + 1)
for i in range(n):
    p[i + 1] = p[i] + a[i]

Endi har bir so‘rov bitta ayirish:

# l..r (1 dan sanaganda)
print(p[r] - p[l - 1])

Tayyorgarlik O(n), har so‘rov O(1), jami O(n + q).

Nega p ning uzunligi n + 1

p[0] = 0 — «hech narsa qo‘shilmagan» holat. Shu qo‘shimcha katak
l = 1 bo‘lganda alohida shart yozishdan qutqaradi.

Ikki o‘lchovli prefiks

Jadvalda to‘rtburchak yig‘indisi ham shu fikr bilan topiladi:

S = p[r2][c2] - p[r1-1][c2] - p[r2][c1-1] + p[r1-1][c1-1]

Oxirgi qo‘shiluvchi — ikki marta ayirilgan burchakni qaytarish.

Farqlar massivi (teskari fikr)

«l..r oralig‘iga +x qo‘sh» turidagi ko‘p so‘rov bo‘lsa:

d = [0] * (n + 2)
# har so‘rovda:
d[l] += x
d[r + 1] -= x
# oxirida bir marta:
joriy = 0
for i in range(1, n + 1):
    joriy += d[i]
    a[i] = joriy

Bu ham O(n + q).

Misol

n, q = map(int, input().split())
a = list(map(int, input().split()))
p = [0] * (n + 1)
for i in range(n):
    p[i + 1] = p[i] + a[i]
for _ in range(q):
    l, r = map(int, input().split())
    print(p[r] - p[l - 1])

Mashq masalalari

✓KodMasalaQiyinlik
AL06-1 Oraliq yig‘indilari Boshlang‘ich
AL06-2 Nol yig‘indili oraliqlar O‘rta
AL06-3 Muvozanat nuqtasi Oson
AL06-4 To‘g‘ri to‘rtburchak yig‘indisi O‘rta
AL06-5 Oraliqqa qo‘shish O‘rta
B104 Prefiks yig‘indi O‘rta

Nazorat savollari

1 Prefiks yig‘indi bilan bitta so‘rovga javob berish murakkabligi qanday? Bitta to‘g‘ri javob
2 `l` dan `r` gacha yig‘indi qanday topiladi (1 dan sanaganda)? Bitta to‘g‘ri javob
3 Prefiks massivining uzunligi n + 1 bo‘lishi `p[0] = 0` uchun kerak. To‘g‘ri yoki noto‘g‘ri
4 a = [1, 2, 3, 4] uchun p massivi qanday bo‘ladi? Kod nima chiqaradi 
p = [0] * 5
for i in range(4):
    p[i + 1] = p[i] + a[i]
print(p)
5 a = [1, 2, 3, 4, 5] bo‘lsa, 2 dan 4 gacha (1 dan sanaganda) yig‘indi nechchi? Qisqa javob — yoziladi
6 Prefiks massivini qurish uchun bo‘sh joyga nima yoziladi? Bo‘sh joyni to‘ldirish 
for i in range(n):
    p[i + 1] = ____ + a[i]
7 Prefiks yig‘indi qaysi masalalarda yordam beradi? Bir nechta to‘g‘ri javob

Bir nechta javob to‘g‘ri bo‘lishi mumkin.

8 Prefiks yig‘indi ishlatilgan yechimning umumiy murakkabligi qanday? Bitta to‘g‘ri javob
9 «Oraliqqa qiymat qo‘shish» turidagi so‘rovlar uchun farqlar massivi ishlatiladi. To‘g‘ri yoki noto‘g‘ri
10 Nega har so‘rovda oddiy sikl bilan sanash yaramaydi? Bitta to‘g‘ri javob

Javoblar serverda tekshiriladi. Katta-kichik harf, apostrof shakli va ortiqcha bo‘shliq ahamiyatsiz.