32-dars: Fenwick daraxti

4-darajaPlatina — dinamik programmalash25–32 darslar

HayotdaDo'kon

Do’kon direktori kun bo’yi ikki xil savol beradi. Birinchisi: «uchinchi kundan yettinchisigacha jami qancha?» Ikkinchisi: «beshinchi kunning raqamini tuzat, u xato yozilgan». Prefiks jadvali birinchi savolga zo’r javob beradi — lekin ikkinchisi uni har safar buzib tashlaydi.

Bu darsdan keyin siz

• prefiks jadvali qayerda yetmay qolishini ayta olasiz
• Fenwick daraxtini quryasiz va ikki amalini yozasiz
• i & (-i) nima qilishini tushuntirasiz

Avval qo’lda

Avval qo‘lda

~7 daqiqa·yakka·Katakli qog'oz

Sakkizta katak chizing va 1 dan 8 gacha raqamlang. Har katak ostiga uning ikkilik yozuvini yozing: 1 = 001, 2 = 010, 3 = 011 va hokazo.

Endi har son uchun eng past yoqilgan bit qiymatini yozing: 1 uchun 1, 2 uchun 2, 3 uchun 1, 4 uchun 4, 6 uchun 2. Bu sonlar nimani eslatadi?

Nimani sezishingiz kerak

Ular 1, 2, 4 va 8 — ikkining darajalari. Fenwick daraxtida aynan shu son har katak nechta elementni qamrashini bildiradi.

Kompyuter yopiq. Bu mashq tugamaguncha kod ochilmaydi.

Prefiks jadvali qayerda yetmaydi

5-darsda prefiks yig’indi jadvalini qurgan edik: so’rov bitta ayirish, ya’ni deyarli bepul. Lekin bitta son o’zgarsa, undan keyingi barcha prefikslar buziladi.

Ikki chekka yechim bor va ikkalasi ham bir tomondan yaxshi, bir tomondan yomon.

Usul	So’rov	O’zgartirish
Oddiy massiv	O(n)	O(1)
Prefiks jadvali	O(1)	O(n)
Fenwick daraxti	O(log n)	O(log n)

Fenwick o’rtacha yo’lni tanlaydi va aynan shu uni foydali qiladi: n va q ikkalasi ham 200 ming bo’lganda faqat uchinchi qator sig’adi.

Sekin yechim

Oddiy massiv: o’zgartirish bir amalda bajariladi, so’rov esa oraliqni qaytadan qo’shadi.

sekin.pyNusxalash

1a = [0, 4, 2, 7, 1, 5, 3, 8, 6]2amallar = [(2, 1, 6), (1, 3, 10), (2, 1, 6), (2, 4, 8)]3javoblar = []4for turi, x, y in amallar:5  if turi == 1:6      a[x] = y7  else:8      javoblar.append(sum(a[x:y + 1]))9print(javoblar)

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

Bashorat qilingNusxalash

1a = [0, 4, 2, 7, 1, 5, 3, 8, 6]2amallar = [(2, 1, 6), (1, 3, 10), (2, 1, 6), (2, 4, 8)]3javoblar = []4for turi, x, y in amallar:5  if turi == 1:6      a[x] = y7  else:8      javoblar.append(sum(a[x:y + 1]))9print(javoblar)

Sizning bashoratingizTekshirish

Javobni ko'rish

[22, 25, 23]

Massiv 1 dan indekslanadi, shuning uchun boshida nol turibdi. Uchinchi element 7 dan 10 ga o'zgargach, birinchi so'rov javobi 22 dan 25 ga ko'tarildi.

Nega sekin

Har so’rov oraliq uzunligiga proporsional. n va q ikkalasi ham 200000 bo’lganda bu 40 milliard amal.

Sig‘adimi?

Bir soniyada taxminan 10⁸ oddiy amal bajariladi.

Yechim	n = 1 000	n = 200 000
Har so‘rovda qayta qo‘shishn^2	10⁶sig‘adi	10¹⁰sig‘maydi
Fenwick daraxtin log n	9 966sig‘adi	10⁶sig‘adi

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

Fenwick daraxti

Fenwick daraxtiFenwick tree

Yig’indilarni turli uzunlikdagi bo’laklarda saqlaydigan massiv. Boshqa nomi — binar indeksli daraxt.

Butun g’oya bitta ifodada: daraxt[i] — i dan orqaga qarab i & (-i) ta elementning yig’indisi.

i & (-i) — indeksning ikkilik yozuvidagi eng past yoqilgan bit. Masalan 12 = 1100, demak 12 & (-12) = 4: o’n ikkinchi katak to’rtta elementni qamraydi.

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

Bashorat qilingNusxalash

1for i in [1, 2, 3, 4, 6, 8, 12]:2  print(i, bin(i)[2:].rjust(4, "0"), i & (-i))

Sizning bashoratingizTekshirish

Javobni ko'rish

1 0001 1
2 0010 2
3 0011 1
4 0100 4
6 0110 2
8 1000 8
12 1100 4

Ikkining darajalari eng ko'p elementni qamraydi, toq sonlar esa faqat bittasini. Shuning uchun daraxt bir tekis emas — u aynan ikkilik yozuvga moslashgan.

Tez yechim

Ikki yurish bor va ikkalasi ham i & (-i) bilan boshqariladi. qosh yuqoriga ko’tariladi — bu elementni o’z ichiga oladigan barcha bo’laklarni yangilaydi. yigindi pastga tushadi — bir-birining ustiga tushmaydigan bo’laklarni qo’shadi.

tez.pyNusxalash

1n = 82a = [0, 4, 2, 7, 1, 5, 3, 8, 6]3daraxt = [0] * (n + 1)4def qosh(i, farq):5  while i <= n:6      daraxt[i] += farq7      i += i & (-i)8def yigindi(i):9  natija = 010  while i > 0:11      natija += daraxt[i]12      i -= i & (-i)13  return natija14for i in range(1, n + 1):15  qosh(i, a[i])16print(daraxt[1:])17print(yigindi(6), yigindi(6) - yigindi(2))

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

Bashorat qilingNusxalash

1n = 82a = [0, 4, 2, 7, 1, 5, 3, 8, 6]3daraxt = [0] * (n + 1)4def qosh(i, farq):5  while i <= n:6      daraxt[i] += farq7      i += i & (-i)8def yigindi(i):9  natija = 010  while i > 0:11      natija += daraxt[i]12      i -= i & (-i)13  return natija14for i in range(1, n + 1):15  qosh(i, a[i])16print(daraxt[1:])17print(yigindi(6), yigindi(6) - yigindi(2))

Sizning bashoratingizTekshirish

Javobni ko'rish

[4, 6, 7, 14, 5, 8, 8, 36]
22 16

yigindi(6) faqat ikkita katakni o'qidi: 6 va 4. Oraliq yig'indisi esa ikki prefiksning ayirmasi — 5-darsdagi hiyla shu yerda ham ishlaydi.

▲Bu yerda xato qilishadi

qosh(i, farq) elementni o’rnatmaydi, unga farq qo’shadi. Shuning uchun i-elementni x ga o’zgartirish uchun qosh(i, x - a[i]) yozib, so’ng a[i] = x qilish kerak. Bu eng ko’p uchraydigan xato.

Fenwick 1 dan indekslanadi va bu majburiy: 0 & (-0) = 0 bo’lgani uchun nolinchi indeksda sikl abadiy aylanadi.

Sinab ko’r

Vizualda har element qo’shilganda qaysi kataklarga tegishini kuzating. Pastki qator — har katak nechta elementni qamrashi.

Fenwick daraxti

Har katak turli uzunlikdagi bo'lakni saqlaydi — pastdagi qatorga qarang.

Fenwick daraxti yig'indilarni bo'laklab saqlaydi; bo'lak uzunligi indeksning eng past yoqilgan bitiga teng.

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

1. Pastki qator — har katak nechta elementni qamrashi: bu indeksning ikkilik yozuvidagi eng past yoqilgan bit, ya'ni i va -i ning VA amali.
2. 1-element (4) qo'shildi. U 4 ta katakka tegdi: 1, 2, 4, 8 — o'z ichiga olganlarining hammasi.
3. 2-element (2) qo'shildi. U 3 ta katakka tegdi: 2, 4, 8 — o'z ichiga olganlarining hammasi.
4. 3-element (7) qo'shildi. U 3 ta katakka tegdi: 3, 4, 8 — o'z ichiga olganlarining hammasi.
5. 4-element (1) qo'shildi. U 2 ta katakka tegdi: 4, 8 — o'z ichiga olganlarining hammasi.
6. 5-element (5) qo'shildi. U 3 ta katakka tegdi: 5, 6, 8 — o'z ichiga olganlarining hammasi.
7. 6-element (3) qo'shildi. U 2 ta katakka tegdi: 6, 8 — o'z ichiga olganlarining hammasi.
8. 7-element (8) qo'shildi. U 2 ta katakka tegdi: 7, 8 — o'z ichiga olganlarining hammasi.
9. 8-element (6) qo'shildi. U 1 ta katakka tegdi: 8 — o'z ichiga olganlarining hammasi.
10. 1 dan 6 gacha yig'indi so'raldi. Faqat 2 ta katak qo'shildi: 6, 4. Javob 22 — oltita emas, ikkita o'qish.
11. Har ikki yurish ham ko'pi bilan log n qadam: har qadamda ikkilik yozuvdagi bitta bit o'chadi yoki qo'shiladi. Shu sababli o'zgartirish ham, so'rov ham tez.

massiv

4021721354358667

fenwick

00000000

qamrov

12141218

Pastki qator — har katak nechta elementni qamrashi: bu indeksning ikkilik yozuvidagi eng past yoqilgan bit, ya'ni i va -i ning VA amali.

Tegilgan katak0

OrqagaO‘ynatishOldinga1/11Qayta boshlash

Xatoni toping

▲Tuzoq — xatoni toping

32 / 40

Masalai-elementni x ga o'zgartiring.

Taklif qilingan yechim

1. 1Fenwick daraxti qurilgan, a massivi ham saqlanmoqda.
2. 2O‘zgartirish uchun qosh(i, x) chaqiramiz.
3. 3Keyin a[i] = x deb yozamiz.
4. 4So‘rovlar avvalgidek ishlayveradi.

Bu javobning 2-qismi noto'g'ri. qosh qiymatni o'rnatmaydi, unga FARQ qo'shadi. qosh(i, x) yozilsa eski qiymat joyida qoladi va ustiga x qo'shiladi. To'g'risi: qosh(i, x - a[i]) — ya'ni faqat o'zgarish miqdori.

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

Javobni ko'rsatish

O’zingizni sinang

1Prefiks jadvali qayerda yetmay qoladi?

Javobni ko'rish

Ma’lumot o’zgarganda. Bitta son o’zgarsa undan keyingi barcha prefikslar buziladi va jadvalni qaytadan qurish kerak bo’ladi.

2i & (-i) nima beradi?

Javobni ko'rish

Indeksning ikkilik yozuvidagi eng past yoqilgan bitni. Fenwickda bu son katak nechta elementni qamrashini bildiradi.

3Nega Fenwick 1 dan indekslanadi?

Javobni ko'rish

0 & (-0) = 0, demak nolinchi indeksda sikl hech qachon siljimaydi va abadiy aylanadi.

4Elementni yangi qiymatga o'rnatish uchun nima qilinadi?

Javobni ko'rish

qosh(i, yangi - eski) chaqiriladi. qosh qiymatni o’rnatmaydi, farq qo’shadi — shuning uchun eski qiymatni alohida saqlab yurish kerak.

5Oraliq yig'indisi qanday olinadi?

Javobni ko'rish

Ikki prefiksning ayirmasi: yigindi(r) - yigindi(l - 1). Bu 5-darsdagi prefiks hiylasining o’zi.

Masalalar

Masalalar

3 ta

• Dynamic Range Sum QueriesCSES 1648o'rta

  Darsdagi masalaning o‘zi. Kirishni tez o‘qing: sys.stdin.buffer.

• Range Update QueriesCSES 1651qiyin

  Teskari o‘ylang: farqlar massivi ustida Fenwick quring, unda oraliq yangilash bitta amalga aylanadi.

• Inversion CountCodeforces 1042Dqiyin

  Prefiks yig‘indi + Fenwick. Qiymatlarni siqib, indekslarga aylantirish kerak.

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

Topshiriq

Topshiriq — darajangizni tanlang

Asos5–7-sinfMustahkam8–9-sinfChuqur10–11-sinf

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

1 dan 16 gacha sonlarning ikkilik yozuvini va i & (-i) qiymatini jadvalga yozing. Qaysi indekslar eng ko’p elementni qamraydi va nega?

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

32-fenwick masalasini yeching. qosh(i, x) va qosh(i, x - a[i]) variantlarini ikkalasini ham sinang va javoblari qaysi testda farq qilishini toping.

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

Fenwickni yig’indi emas, maksimum uchun moslashtiring. Ishlay oladimi? Qaysi amal muammo tug’diradi 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.

Darsni tugatdim