Algoritmlar va berilganlar strukturasi

OʻZBEKISTON RESPUBLIKASI OLIY VA O‘RTA MAXSUS
TA’LIM VAZIRLIGI
MIRZO ULUG‘BEK NOMIDAGI MILLIY UNIVERSITETININIG
JIZZAX FILIALI



AMALIY MATEMATIKA FAKULTETI


«KOMPYUTER ILMLARI VA DASTURLASHTIRISH» kafedrasi

“ALGORITMLAR VA BERILGANLAR STRUKTURASI”

FANIDAN
MUSTAQIL ISH
Mavzu: ____________________________________________________
Bajardi: “____________” yoʻnalishi __kurs___ guruh________
talabasi______________________________________
Tekshirdi:_________________________________________

Jizzax – 2023

Mavzu: Fenwick daraxti

Reja:

1.Fenvik daraxtlar haqida umumiy tushunch.
2. Diapazon so'rovi
3.Nuqtalarni yangilash
4. Daraxt qurish
5.Amaliy qism.


Fenwick daraxti yoki ikkilik indeksli daraxt (BIT) -bu elementlarni samarali yangilash va raqamlar jadvalidagi prefiks summalarini hisoblash mumkin bo'lgan ma'lumotlar tuzilmasi .Bu tuzilma 1989 yilda Boris Ryabko tomonidan taklif qilingan [1] qoʻshimcha modifikatsiyasi 1992 yilda chop etilgan. [2] Keyinchalik u 1994 yilgi maqolasida ushbu tuzilmani tasvirlab bergan Piter Fenvik nomidan Fenvik daraxti nomi bilan maʼlum boʻldi . [3]
Yassi raqamlar qatori bilan solishtirganda, Fenwick daraxti ikkita operatsiya o'rtasida ancha yaxshi muvozanatga erishadi: elementlarni yangilash va prefiks yig'indisini hisoblashning tekis massivini n raqamlar elementlarni yoki prefiks summalarini saqlashi mumkin. Birinchi holda, prefiks summalarini hisoblash chiziqli vaqtni talab qiladi; ikkinchi holatda massiv elementlarini yangilash chiziqli vaqtni talab qiladi (har ikki holatda ham boshqa amal doimiy vaqtda bajarilishi mumkin). Fenwick daraxtlari ikkala operatsiyani ham bajarishga imkon beradi vaqt. Bunga raqamlarni daraxt shaklida ifodalash orqali erishiladin n+1 daraxtdagi har bir tugunning qiymati massivning asosiy (shu jumladan) indeksidan tugun indeksi (eksklyuziv)gacha bo'lgan prefiks yig'indisi bo'lgan tugunlar. Daraxtning o'zi yashirin va massiv sifatida saqlanishi mumkinn raqamlar, massivdan yashirin ildiz tugunlari olib tashlangan. Daraxt tuzilishi elementni qidirish, elementni yangilash, prefiks yig'indisi va diapazon yig'indisi operatsiyalarini faqat foydalanishga imkon beradi. tugunga kirish.
Elementlar jadvalini hisobga olgan holda, ba'zida ba'zi bir assotsiativ ikkilik operatsiyalar bo'yicha har bir indeksgacha bo'lgan qiymatlarning umumiy miqdorini hisoblash maqsadga muvofiqdir (butun sonlarni qo'shish eng keng tarqalgan). Fenvik daraxtlari asosiy qiymatlar jadvaliga o'zgartirishlar kiritishga ruxsat berish va barcha keyingi so'rovlar ushbu o'zgarishlarni aks ettirishga qo'shimcha ravishda har qanday indeks bo'yicha ishlaydigan jami so'rov qilish usulini taqdim etadi.

Fenvik daraxtlari, ayniqsa, ishlab chiqarilgan har bir belgining sonini saqlaydigan arifmetik kodlash algoritmini amalga oshirish uchun mo'ljallangan va ularni berilgan belgidan kamroq belgilarning yig'indisi ehtimoliga aylantirishi kerak . U qo'llab-quvvatlaydigan operatsiyalarni rivojlantirish, birinchi navbatda, bu holatda foydalanishga turtki bo'ldi.
Fenwick daraxtidan foydalanish faqat talab qiladiO(jurnal⁡n)  stalgan jami yig'indini yoki umuman olganda, har qanday qiymatlar diapazonining yig'indisini (noldan boshlanishi shart emas) hisoblash uchun operatsiyalar. Shuningdek, jami yig'indilarni tez hisoblash uchun ushbu ma'lumotlar strukturasining kengaytmalarini qurish mumkind d- o'lchovli massivlarO(jurnald⁡n)  vaqt. [4]
Fenwick daraxti bir asosli massivni hisobga olgan holda eng oson tushuniladi A[n] bilann A[n] elementlar. Tegishli Fenwick daraxti born+1 n+1 ildizida yashirin tugun 0 bo'lgan tugunlar. Har bir darajak k daraxtning yig'indisiga mos keladigan indeksli tugunlarni o'z ichiga oladik k2 ning alohida kuchlari (bilank=0 k=0 bo'sh summani ifodalovchi 0). Masalan, darajak=1 k=1 tugunlarni o'z ichiga oladi1=20,2=21,4=22,...  va darajak=2 k=2 tugunlarni o'z ichiga oladi3=21+20,5=22+20,6=22+21,...  Berilgan tugunning ota-onasini uning indeksidagi eng kichik quvvat 2 ga mos keladigan oxirgi o'rnatilgan bitni (LSB) tozalash orqali topish mumkin. 
Masalan, 6 = 110 _{2 ning} ota-onasi 4 = 100 ₂ ga teng .
Quyidagi diagrammada 15 elementli A massiviga mos keladigan 16 tugunli Fenvik daraxtining tuzilishi ko'rsatilgan:

1-rasm. 15 tugunli A massivining diapazon yig'indisini o'z ichiga olgan 16 tugunli Fenvik daraxti tasviri
M ayliA(i,j]={A[k]}k=i+1j . Indeksdagi tugunning qiymatii i dagi elementlarning diapazon yig'indisiga mos keladiA(parent(i),i]  , ya'ni A qiymatlari ota-ona indeksidan keyin joriy tugun indeksigacha, shu jumladan. ElementlarA(parent(i),i]  joriy tugun [3] uchun "mas'uliyat doirasi" hisoblanadi va iboratlsb(i)=(i & (−i))  (qaerda & bit bo'yicha VAni bildiradi) elementlar. E'tibor bering, ushbu diapazondagi indekslar to'g'ridan-to'g'ri bolalarga mos kelmaydii i: masalan, 2-tugun uchun javobgarlik doirasiA(0,2]={A[1],A[2]}  lekin 1-tugun 2-tugunning bolasi emas. 0-tugun boʻsh diapazon yigʻindisini oʻz ichiga oladi.A(0,0]={}  0 qiymati bilan.
Odatda, Fenwick daraxti ikkilik to'pni amalga oshirishga o'xshash tekis massiv yordamida yashirin ma'lumotlar strukturasi sifatida amalga oshiriladi . Ushbu ko'rinishda 0 ildiz tuguni o'tkazib yuborilgan va massiv indekslari daraxtdagi tugun indekslariga to'g'ridan-to'g'ri mos keladi (1-asosli indekslashdan foydalangan holda).
Qadriyatlar jadvali ustida Fenwick daraxtini qurishning dastlabki jarayoni davom etadiO(n) O(n) vaqt. Boshqa samarali operatsiyalar, agar barcha qiymatlar ijobiy bo'lsa, qiymat indeksini yoki barcha qiymatlar manfiy bo'lmasa, berilgan qiymatga ega barcha indekslarni topishni o'z ichiga oladi. Bundan tashqari, barcha qiymatlarni doimiy omil bilan masshtablash qo'llab-quvvatlanadiO(n) O(n) vaqt.