Asosiy mazmunga o'tish
STEAM AcademySTEAM Academy

5-dars: Massiv va prefiks yig'indi

1-darajaBronza — algoritmik fikrlash1–8 darslar

Bu darsdan keyin siz

  • prefiks yig’indi jadvalini qurasiz va undan oraliq yig’indisini olasiz
  • «oldindan hisoblab qo’yish» g’oyasini boshqa masalalarda taniysiz
  • jadval chegaralarida bir birlik xatoga yo’l qo’ymaysiz

Avval qo’lda

“Avval qo’lda” bo'limiga havola

Avval qo‘lda

~5 daqiqajuftlikda6 ta kartochka va qalam

Oltita kartochkaga sonlar yozing, masalan 4 2 7 1 5 3, va ularni qatorga tering. Ostiga yettinchi qator qo’shing: birinchi katakka 0, keyingi har katakka oldingi katak qiymati + tepasidagi son.

Endi sinfdoshingiz «ikkinchidan to’rtinchigacha yig’indi qancha?» deb so’rasin. Siz qo’shmang — pastki qatordan ikkita sonni oling va ayiring.

Nimani sezishingiz kerak

Javob bitta ayirishda chiqdi. Qanchalik uzun oraliq so’ralsa ham ish hajmi o’zgarmaydi — bu jadvalning butun ma’nosi.

Kompyuter yopiq. Bu mashq tugamaguncha kod ochilmaydi.

Sekin yechim

“Sekin yechim” bo'limiga havola

Har so’rovda oraliqni qaytadan qo’shamiz. Yechim to’g’ri, bir qatorga sig’adi va uni tushuntirish shart emas.

sekin.py
savdo = [4, 2, 7, 1, 5]sorovlar = [(0, 2), (1, 1), (0, 4)]for chap, ong in sorovlar:  print(sum(savdo[chap:ong + 1]))

Avval o'ylang: bu kod nima chiqaradi? Ishga tushirishdan oldin yozing.

Bashorat qiling
savdo = [4, 2, 7, 1, 5]sorovlar = [(0, 2), (1, 1), (0, 4)]for chap, ong in sorovlar:  print(sum(savdo[chap:ong + 1]))
Javobni ko'rish
13
2
19

Kesmaning o'ng chegarasi Python'da kirmaydi, shuning uchun ong + 1 yoziladi. Bu bitta belgi eng ko'p unutiladigan joy.

Nega sekin

“Nega sekin” bo'limiga havola

sum() oraliqdagi har sonni qaytadan o’qiydi. Bitta so’rov uchun bu arzimas ish, lekin so’rovlar soni ham, ro’yxat uzunligi ham 200000 gacha bo’lishi mumkin.

Sig‘adimi?

Bir soniyada taxminan 10⁸ oddiy amal bajariladi.

Yechimn = 100n = 5 000n = 200 000
Har so‘rovda qayta qo‘shishn^210 000sig‘adi10⁷sig‘adi10¹⁰sig‘maydi
Jadval qurib, ayirishn100sig‘adi5 000sig‘adi200 000sig‘adi

Yashil — yechim o‘tadi. Sariq — chegarada, konstanta va til muhim bo‘lib qoladi. Qizil — bu yechim bilan bormaydi, boshqasini qidiring.

Eng yomon holatda har so’rov butun ro’yxatni o’qiydi: 200000 × 200000, ya’ni 40 milliard amal. Ayni bir sonlar millionlab marta qayta qo’shiladi — bu ishning katta qismi behuda.

Tez yechim

“Tez yechim” bo'limiga havola
prefiks yig'indiprefix sum

p[k] — ro’yxatning birinchi k ta elementi yig’indisi. p[0] har doim nol: hech narsa olinmagan holat.

Jadval bir marta quriladi, keyin har oraliq bitta ayirishga aylanadi: [l..r] yig’indisi p[r+1] − p[l] ga teng.

tez.py
savdo = [4, 2, 7, 1, 5]prefiks = [0] * (len(savdo) + 1)for i in range(len(savdo)):  prefiks[i + 1] = prefiks[i] + savdo[i]for chap, ong in [(0, 2), (1, 1), (0, 4)]:  print(prefiks[ong + 1] - prefiks[chap])

Nega ishlaydi: p[r+1] boshidan r gacha hamma narsani o’z ichiga oladi, p[l] esa l dan oldingi ortiqcha qismni. Ayirsak, aynan kerakli oraliq qoladi.

Avval o'ylang: bu kod nima chiqaradi? Ishga tushirishdan oldin yozing.

Bashorat qiling
savdo = [4, 2, 7, 1, 5]prefiks = [0] * (len(savdo) + 1)for i in range(len(savdo)):  prefiks[i + 1] = prefiks[i] + savdo[i]print(prefiks)print(prefiks[3] - prefiks[0])
Javobni ko'rish
[0, 4, 6, 13, 14, 19]
13

Jadval ro'yxatdan bitta uzun: boshida nol turadi. Aynan shu nol tufayli chap chegarasi 0 bo'lgan so'rovni alohida holat sifatida yozish kerak emas.

Sinab ko’r

“Sinab ko’r” bo'limiga havola

Vizualda avval jadval to’ladi, keyin so’rovlar keladi. Amal hisoblagichiga qarang: jadval qurilishi bir marta qimmatga tushadi, keyin narx nolga yaqinlashadi.

Prefiks yig'indi — bir marta hisobla, ming marta ishlat

Avval jadval to'ladi, keyin har so'rov bitta ayirishga aylanadi.

Prefiks jadvali sakkizta qo'shish bilan quriladi, keyin har oraliq yig'indisi bitta ayirish bilan topiladi.

Algoritmning har qadami quyidagi ro‘yxatda matn sifatida ham berilgan — vizual faqat shu qadamlarni chizadi, yangi ma’lumot qo‘shmaydi.

  1. Pastdagi qator — prefiks yig'indi. p[k] = birinchi k ta sonning yig'indisi.
  2. p[1] = p[0] + 4 = 4. Har son faqat bir marta qo'shiladi.
  3. p[2] = p[1] + 2 = 6. Har son faqat bir marta qo'shiladi.
  4. p[3] = p[2] + 7 = 13. Har son faqat bir marta qo'shiladi.
  5. p[4] = p[3] + 1 = 14. Har son faqat bir marta qo'shiladi.
  6. p[5] = p[4] + 5 = 19. Har son faqat bir marta qo'shiladi.
  7. p[6] = p[5] + 3 = 22. Har son faqat bir marta qo'shiladi.
  8. p[7] = p[6] + 8 = 30. Har son faqat bir marta qo'shiladi.
  9. p[8] = p[7] + 2 = 32. Har son faqat bir marta qo'shiladi.
  10. Jadval tayyor — 8 ta qo'shish sarfladik. Endi har so'rovga javob BIR AMALDA chiqadi.
  11. [2..5] yig'indisi = p[6] - p[2] = 22 - 6 = 16. Bitta ayirish.
  12. [0..7] yig'indisi = p[8] - p[0] = 32 - 0 = 32. Bitta ayirish.
  13. Ming so'rov bo'lsa ham har biri bitta ayirish. Oldindan hisoblab qo'yish — birinchi va eng ko'p ishlatiladigan hiyla.
sonlar
4021721354358627
prefiks
0
javob

Pastdagi qator — prefiks yig'indi. p[k] = birinchi k ta sonning yig'indisi.

Amal0

1/13

Xatoni toping

“Xatoni toping” bo'limiga havola

Tuzoq — xatoni toping

5 / 40

MasalaPrefiks jadvali qurilgan. [l..r] oraliq yig'indisini toping.

Taklif qilingan yechim

Bu javobning 3-qismi noto'g'ri. p[r] boshidan r gacha emas, r dan OLDIN gacha bo'lgan yig'indini beradi — chunki p[k] birinchi k ta element, ya'ni 0 dan k-1 gacha. r-elementni ham qo'shish uchun p[r+1] kerak. To'g'ri javob: p[r+1] - p[l].

Javobning qaysi qismi noto'g'ri? Bosib belgilang.

O’zingizni sinang

“O’zingizni sinang” bo'limiga havola

1Nega prefiks jadvali ro'yxatdan bitta uzun bo'ladi?

Javobni ko'rish

Boshida p[0] = 0 turadi — «hech narsa olinmagan» holat. U bo’lmasa chap chegarasi nol bo’lgan so’rovni alohida ishlash kerak bo’lardi.

2Jadval qurilgandan keyin bitta so'rov nechta amal oladi?

Javobni ko'rish

Ikkita o’qish va bitta ayirish — ya’ni so’rov uzunligiga umuman bog’liq emas. Ming elementli oraliq ham, bitta elementli oraliq ham bir xil narx.

3Ro'yxat so'rovlar orasida o'zgarsa, jadval ishlaydimi?

Javobni ko'rish

Ishlamaydi. Bitta element o’zgarsa, undan keyingi barcha p[k] qiymatlari buziladi. Bunday holat uchun boshqa tuzilma kerak — u 32-darsda keladi.

4n va q ikkalasi ham 200000 bo'lsa, prefiks yechim nechta amal qiladi?

Javobni ko'rish

Taxminan n + q, ya’ni 400 ming. Bu 10⁸ chegarasidan ancha past. Sekin yechim esa 40 milliard amal talab qilgan bo’lardi.

5«Oldindan hisoblab qo'yish» g'oyasini bir gapda ayting.

Javobni ko'rish

Ko’p marta so’raladigan javobni bir marta hisoblab saqlab qo’yish. Tayyorgarlik qimmat, lekin u bir marta to’lanadi va keyin har so’rov arzon bo’ladi.

Masalalar

“Masalalar” bo'limiga havola

Masalalar

3 ta

  • Static Range Sum QueriesCSES 1646oson

    Darsdagi yechimning o‘zi. Indekslar 1 dan boshlanishiga e‘tibor bering.

  • Subarray Sums ICSES 1660o'rta

    Prefiks yig‘indi + «kerakli sherikni qidirish». 2-darsdagi juftliklar bilan bir xil fikr.

  • Forest QueriesCSES 1652o'rta

    Ikki o‘lchovli prefiks. To‘rtburchak yig‘indisi to‘rtta qiymatdan yig‘iladi.

Lokal mashq: mashqlar/05-prefiks/ — masala matni, testlar va tekshir.py. Avval sekin.py ni o‘zingiz yozing, keyin tayyorini oching.

Topshiriq

“Topshiriq” bo'limiga havola

Topshiriq — darajangizni tanlang

Asos · 5–7-sinf — Vizual va aniq ko'rsatmali

3 1 4 1 5 9 2 6 ro’yxati uchun prefiks jadvalini qog’ozda quring. Keyin uchta oraliq yig’indisini jadval bilan hisoblang va to’g’riligini oddiy qo’shish bilan tekshiring.

Mustahkam · 8–9-sinf — Matnli masala, o'zingiz tuzasiz

05-prefiks masalasini yeching. sekin.py ni katta test bilan yurgizib vaqtini o’lchang, keyin tez.py ni yozing va ikki vaqtni yonma-yon yozib qo’ying.

Chuqur · 10–11-sinf — Algoritmik, chegara holatlari bilan

Prefiks g’oyasini ko’paytmaga o’tkazing: [l..r] oraliqdagi sonlar ko’paytmasini bitta amalda topish mumkinmi? Qaysi holatda usul buziladi va nega? Javobingizni misol bilan asoslang.

Darsni belgilash uchun JavaScript kerak. Bu progressni saqlash uchun ishlatiladi — darslikning o'zi JavaScript'siz ham to'liq o'qiladi.