Fenwick daraxti

Информация о документе

Цена	10000UZS
Размер	286.9KB
Покупки	0
Дата загрузки	06 Ноябрь 2026
Расширение	docx
Раздел	Курсовые работы
Предмет	Педагогика

Fenwick daraxti

Купить

$Mavzu: “Fenwick daraxti” MUNDARIJA KIRISH ........................................................................................................... 3 1.1.Daraxt tushunchasi. ............................................................................. 5 B daraxtda element izlash .............................................................................. 13 void btree_lookup(struct btree *tree, int key, ................................................ 13 struct btree **node, int *index) ..................................................................... 13 { ..................................................................................................................... 13 int i; ................................................................................................................ 13 for (i = 0; i < tree->nkeys && key > tree->key[i]; ) { ................................... 13 i++; ................................................................................................................ 13 } ..................................................................................................................... 13 if (i < tree->nkeys && key == tree->key[i]) { .............................................. 13 *node = tree; .................................................................................................. 13 *index = i; ...................................................................................................... 13 return; ............................................................................................................ 13 } ..................................................................................................................... 13 if (!tree->leaf) { ............................................................................................. 13 /* Disk read tree->child[i] */ ......................................................................... 13 btree_lookup(tree, key, node, index); ............................................................ 13 } else { ........................................................................................................... 13 *node = NULL; } .......................................................................................... 13 II.BOB. DARAXTNING STRUKTURALARI VA DASTURI. .................. 14 2.2. Fenwick daraxti dasturiy tahlili. ....................................................... 17 Ikkilik indeksli daraxt (Fenwick Tree) massivning prefiks yig'indisini tezda hisoblash uchun ishlatilishi mumkin bo'lgan samarali ma'lumotlar strukturasidir.Agar massivda mavjud qiymatlar o'zgaruvchan bo'lsa. m . e .qiymatlarni Fenwick daraxti yordamida o'zgartirish mumkin, bu juda foydali.Odatda, agar biz massivdagi 0 dan n gacha bo'lgan barcha raqamlarning yig'indisini hisoblamoqchi bo'lsak, biz indeks-0 dan boshlab har bir elementni ko'rib chiqamiz va indeks-n ga qadar barcha elementlarni qo'shishni davom ettiramiz. Bu O(n) vaqtini oladi va o'lcham juda katta bo'lsa va biz ko'p so'rovlarni bajarishimiz kerak bo'lganda samarali emas.Buning bir yechimi prefiks sum massividan foydalanishdir. Prefiks yig'indisi massivi oldindan hisoblangan massiv bo'lib, unda har qanday indeksdagi qiymat asl massivdagi 0 dan ushbu indeksgacha bo'lgan barcha raqamlar yig'indisiga teng bo'ladi. Agar bizdan x va y o'rtasidagi indekslarning umumiy yig'indisini olishni so'ragan so'rovni olsak, biz x-1 indeksidagi prefiks summasini y indeksidagi prefiks yig'indisidan ayirishimiz kerak, bu bizga x indekslaridagi elementlarning yig'indisini beradi. y ga. Bu faqat 2 ta operatsiyani oladi va shuning uchun biz O (1) vaqtida diapazon summasini$

olishimiz mumkin. Ammo diqqatga sazovor narsa shundaki, agar indeksdagi
qiymat io'zgarsa, kattaroq indekslar uchun barcha prefiks summalari io'zgaradi va
bu O(N) vaqtini oladi.Xulosa qilib aytadigan bo'lsak, birinchi yondashuv O(N)har
qanday berilgan indekslar orasidagi barcha elementlarning yig'indisini hisoblash
uchun vaqt talab etadi, ammo O(1)har qanday elementni yangilash uchun vaqt
kerak bo'ladi. Prefiks yig'indisidan foydalangan holda ikkinchi
yondashuvda, O(1)har qanday berilgan indekslar orasidagi barcha elementlarning
yig'indisini hisoblash uchun vaqt kerak bo'ladi, lekin O(N)agar dastlabki
massivdagi biron bir element o'zgargan bo'lsa, prefiks yig'indisi qatorini yangilash
uchun vaqt kerak bo'ladi.Endi savol shundaki, ikkalamiz o'rtasida muvozanat
bo'lishi mumkinmi? ya'ni, har qanday elementni yangilash vaqtida o'rtacha vaqt
murakkabligi va prefiks summalarini hisoblash uchun o'rtacha vaqt murakkabligi
bormi? Ikkilik indeksli daraxt yoki Fenwick daraxti bu savolning bir yechimidir. 20
ADABIYOTLAR RO’YXATI ...................................................................... 22
ILOVALAR ................................................................................................... 23
ILOVA 1. Modul N1 boshlang’ich kodi. ............................................... 23

KIRISH
Mavzuning dolzarbligi . Bugungi kunda ma‘lumotlar oqimining ko‘pligi
tufayli ularni qisqa vaqt ichida qayta ishlash muommosi ham ortib bormoqda.
Hozirgi vaqtda axborot- kommunikasiya vositalari barcha turdagi tashkilot va
muassasalarga shiddat bilan kirib kelmoqda. Axborotlarning haddan tashqari
ko‘pligi bu axborotlarni saqlashda, qayta ishlashda, hamda har xil turdagi
tizimlarni yaratish, ulardan keng foydalanishni va axborot tizimlari yaratishni talab
qiladi. O‘zbekiston Respublikasi Prezidentining 2017 yil 7 fevraldagi PF-4947-son
Farmoni bilan tasdiqlangan 2017-2021 yillarda O‘zbekiston Respublikasini
rivojlantirishning beshta ustuvor yo‘nalishi bo‘yicha harakatlar strategiyasi
mamlakatning davlat va jamiyat rivojlanishi istiqbolini strategik rejalashtirish
tizimiga sifat jihatdan yangi yondashuvlarni boshlab berdi[1]. Unda belgilangan
vazifalar sirasida ta‘lim va fan sohasini rivojlantirish ham aloxida ko‘zda tutilgan.
O‘zbekiston Respublikasi birinchi Prezidentining 2012 yil 21 martdagi
“Zamonaviy axborot-kommunikasiya texnologiyalarini yanada joriy etish va
rivojlantirish chora-tadbirlari to‘g‘risida”gi PQ-1730 Qarori hamda “O‘zbekiston
Respublikasida —Elektron ta‘lim milliy tarmog‘ini yaratish” investision loyihasini
amalga oshirish chora-tadbirlari to‘g‘risida” gi PQ-1740 Qarori va me‘yoriy
hujjatlar asosida algoritmik ta‘minot ishlab chiqish va joriy etish keng ko‘lamli
hisoblanadi. Barcha tashkilot va muassasalarda avtomatlashtirilgan tizimlar
yaratish ulardan keng ko‘lamda foydalanish uchun algoritmlash tillarini o‘rni katta
hisoblanadi.
Axborot tizimlari axborotni to‘plash, saqlash va qayta ishlash uchun, keng
imkoniyatli maqsadlarda samarali foydalanish uchun xizmat qiladi. Zamonaviy
axborotlashtirish tizimi, ma‘lumotlar integratsiyasi konsepsiyasiga asoslangan
katta hajmdagi ma‘lumotlarni saqlash bilan tavsiflanadi va ko‘p sondagi
foydalanuvchilarning turli xildagi talablariga javob berishi kerak bo‘ladi. Axborot
tizimi va axborot texnologiyalarining avtomatlashtirilgan elementlarini qo‘llash va
avtomatlashtirish asosida yangi axborot texnologiyasini yaratish avtomatlashtirish
tizimlarini loyihalashtiruvchilarning asosiy vazifalaridan biri hisoblanadi

3
Fenwick daraxti yoki ikkilik indeksli daraxt (BIT) - bu elementlarni samarali
yangilash va raqamlar jadvalidagi prefiks summalarini hisoblash mumkin bo'lgan
ma'lumotlar tuzilmasi .
Ushbu tuzilma 1989 yilda Boris Ryabko tomonidan taklif qilingan. 1992 yilda
nashr etilgan keyingi o'zgartirish bilan. Keyinchalik u 1994 yilgi maqolasida
ushbu tuzilmani tasvirlab bergan Piter Fenvik nomidan Fenvik daraxti nomi bilan
mashhur bo'ldi .
Yassi raqamlar qatori bilan solishtirganda, Fenwick daraxti ikkita operatsiya
o'rtasida ancha yaxshi muvozanatga erishadi: elementlarni yangilash va prefiks
yig'indisini hisoblash. ning tekis massivi raqamlar elementlarni yoki prefiks
summalarini saqlashi mumkin. Birinchi holda, prefiks summalarini hisoblash
chiziqli vaqtni talab qiladi; ikkinchi holda, massiv elementlarini yangilash chiziqli
vaqtni talab qiladi (har ikkala holatda ham boshqa operatsiya doimiy vaqtda
bajarilishi mumkin). Fenwick daraxtlari ikkala operatsiyani ham bajarishga imkon
beradi vaqt. Bunga raqamlarn i daraxt shaklida ifodalash orqali erishiladi
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 mumkin
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.
Kurs ishining maqsadi: Fenwick daraxti mavzusini o’rganish
Kurs ishining tuzilishi : Kurs ish kirish, 2 bob, 5 bo‘lim, umumiy xulosalar va
tavsiyalar, foydalanilgan adabiyotlar ro‘yhatidan iborat bo‘lib, jami 22 sahifani
tashkil qiladi.
4

I Bob. Daraxt tushunchasi.Daraxtlar grafning xususiy holati.
1.1.Daraxt tushunchasi.
Daraxt - bu bog langan asiklik graf, ya’ni sikllar yo q va uchlar juftligi orasidaʻ ʻ
bitta
yo l bor (29-rasm). Kirishning nol darajasiga ega bo lgan uch daraxtning ildizi,
ʻ ʻ
chiqish nol darajaga ega tugunlar esa barglar deb nomlanadi.
Daraxtlar quyidagi belgilari bilan tavsiflanadi:daraxtda ildiz deb ataluvchi shunday
yagona element mavjudki, unga boshqa elementlardan murojaat mavjud emas;
daraxt ixtiyoriy elementga murojaat (element qiymatini olish) chekli sondagi
ketma-ket murojaatlar yoki ko‘rsatkichlardan o‘tib borish orqali amalga oshiriladi;
1-rasm.Yo’naltirilgan daraxt.
Yo naltirilgan (oriyentirlangan) daraxt - bu faqat bitta vertikal kirish nol darajasiga
ʻ
ega bo lgan (boshqa yoylar unga olib kelmaydigan), boshqa uchlarning kirish
ʻ

5
darajasi 1 bo lgan siklik orgraf (sikllarni o z ichiga olmaydigan yo naltirilganʻ ʻ ʻ
graf).
Daraxtning asosiy tushunchalari .
Ildiz tuguni - daraxtning eng yuqori tuguni (2-tugun).
Ildiz – ixtiyoriy tanlab olingan uchlardan biri.
Barg yoki terminal tuguni – avlodi mavjud bo lmagan tugun. (2,10,5,11,4-
ʻ
tugunlar)
Ichki tugun - bu daraxtga avlodi mavjud bo lgan har qanday tugun .(7,5,9,6-
ʻ
tugunlar).
va shuning uchun barg tuguni emas (18-rasmda 3, 6, 10, 14).
Uchning darajasi - unga tushgan qirralarning soni.
Daraxt osti - bu alohida daraxt sifatida namoyish etilishi mumkin
bo lgan daraxtga o xshash ma’lumotlar strukturasining bir qismidir. T
ʻ ʻ
daraxtining har qanday tuguni va uning barcha nasl tugunlari bilan birga
daraxtining pastki daraxti hisoblanadi. Daraxt osti har qanday tuguni
uchun, yo ushbu kichik daraxtning ildiz tuguniga yo l bo lishi kerak, yo
ʻ ʻ
tugunning o zi ildiz bo lishi kerak.
ʻ ʻ Daraxtdagi darajalar soni balandlik deb
ataladi.
Masalan 1-rasmdagi d araxtning balandligi 3 ga teng.

1.2. Tartiblangan va muvozanatlashgan daraxtlar
AVL daraxt. AVL-daraxt (inglizcha AVL-Tree) bu
muvozanatlashgan ikkilik qidiruv daraxti bo lib, unda quyidagi ʻ
xususiyat qo llab-quvvatlanadi: uning har bir uchlari uchun uning ikkita
ʻ
ostki daraxtining balandligi 1 dan ko p bo lmagan qiymatga farq qiladi.
ʻ ʻ
AVL daraxtlari birinchi marta 1962-yilda AVL daraxtlaridan foydalanishni taklif
qilgan G. M. Adelson-Velskiy va E. M. Landisning ismlarining birinchi harflari
bilan nomlangan.
Uchlarni muvozanatlash - bu |h(L) − h(R)| = 2 chap va o ng
ʻ
pastki daraxtlari balandliklari farqi bo lgan taqdirda, |h(L) − h(R)| ≤ 2 daraxtining
ʻ
xususiyati tiklanishi uchun ushbu uchlarning pastki daraxtidagi ajdod va avlod
munosabatlarini o zgartiradigan amal, aks holda hech narsani o zgartirilmaydi.
ʻ ʻ
Daraxtning balandligi maksimal darajasi, ildizdan tashqi tugunga qadar eng uzun
yo lning uzunligi sifatida aniqlanadi. Ikkilik qidiruv daraxti muvozanatli deyiladi,
ʻ
agar biron bir ugunning chap pastki daraxtining balandligi o ng pastki daraxtning
ʻ
balandligidan ± 1 dan oshmasa.
7

$2-Rasm.AVL DARAXTI AVL daraxtda tugun hosil qilish dasturi. struct avltree *avltree_create(int key,char *value) { struct avltree *node; node = malloc(sizeof(*node)); if (node != NULL) { node->key = key; node->value = value; node->left = NULL; node->right = NULL; node->height = 0; } return node; } 8$ $Tugundan kalit bo yicha izlash funksiyasi ʻ struct avltree *avltree_lookup(struct avltree *tree, int key) { while(tree !=NULL) { if(key == tree->key) { return tree; } else if(key<tree->key) { tree = tree->left; } else { tree = tree->rigth; } } }; Daraxt strukturasi orasida tartiblangan daraxtlar eng keng tarqalgan. Binar (Ikkilik) qidiruv daraxti - tartiblangan daraxt turidir. Ikkilik daraxt - bu har bir tugunda ko pi bilan ikkita avlod (bola) ʻ bo lgan ma’lumotlarning iyerarxik tuzilishi. Odatda, birinchisi ajdod ʻ tuguni, avlodlar esa chap va o ng merosxo rlar deb nomlanadi. ʻ ʻ 9$

2-rasm.Binar(ikkilik daraxt) daraxt.
1.3. Muvozanatlashgan daraxtlar.B daraxt .
B daraxti (inglizcha B-tree) – izlash, qo'shish va o'chirish imkonini beradigan,
juda ko pshoxli muvozanatlashgan qidiruv daraxti. Tugunlari ʻ
n bo'lgan B daraxti O(logn) balandlikka ega bo‘ladi. Tugun shoxlari soni
bittadan bir necha minggacha bo'lishi mumkin (odatda, B-daraxtining
shoxlanish darajasi daraxt ishlaydigan qurilma (disklar) xususiyatlari
bilan belgilanadi). B-daraxtlar O(logn) ko'p dinamik to'plam amallarini o'z
vaqtida bajarish uchun ham ishlatilishi mumkin. B daraxti birinchi marta
1970-yilda R. Bayer va E. Makkreyt tomonidan taklif qilingan.
B daraxt strukturasi. B daraxti mukammal muvozanatlashgan
ya'ni uning barcha barglarining chuqurligi bir xil. B daraxti quyidagi
xususiyatlarga ega ( t – bu daraxt parametrlari, B daraxtining minimal
darajasi deyiladi, 2 dan kam emas ):
Ildizdan tashqari har bir tugun hech bo'lmaganda t-1 kalitni o'z
10

$ichiga oladi va har bir ichki tugun kamida avlodli t tugunlarga ega. Agar daraxt bo'sh bo'lmasa, ildizda kamida bitta kalit bo'lishi kerak. Har bir tugunning kalitlari kamaymaydigan tartibda tartiblangan. Barcha barglar bir xil darajada. 3-RASM. B DARAXT. B daraxtni hosil qilish. struct btree *btree_create() { struct btree *node; node = malloc(sizeof(*node)); node->leaf = 1; node->nkeys = 0; node->key = malloc(sizeof(*node->key) * 2 * T - 1); node->value = malloc(sizeof(*node->value) 2 * T - 1); node->child = malloc(sizeof(*node->child) 2 * T);$ $11 return node; } B daraxtda element izlash void btree_lookup(struct btree *tree, int key, struct btree **node, int *index) { int i; for (i = 0; i < tree->nkeys && key > tree->key[i]; ) { i++; } if (i < tree->nkeys && key == tree->key[i]) { *node = tree; *index = i; return; } if (!tree->leaf) { /* Disk read tree->child[i] */ btree_lookup(tree, key, node, index); } else { *node = NULL; } 12$

II.BOB. DARAXTNING STRUKTURALARI VA DASTURI.
2.1. Fenwick daraxti.
Fenwick daraxti yoki ikkilik indeksli daraxt (BIT) - bu elementlarni samarali
yangilash va raqamlar jadvalidagi prefiks summalarini hisoblash mumkin bo'lgan
ma'lumotlar tuzilmasi .
Ushbu tuzilma 1989 yilda Boris Ryabko tomonidan taklif qilingan. 1992 yilda nashr
etilgan keyingi o'zgartirish bilan. Keyinchalik u 1994 yilgi maqolasida ushbu
tuzilmani tasvirlab bergan Piter Fenvik nomidan Fenvik daraxti nomi bilan mashhur
bo'ldi .
Yassi raqamlar qatori bilan solishtirganda, Fenwick daraxti ikkita operatsiya o'rtasida
ancha yaxshi muvozanatga erishadi: elementlarni yangilash va prefiks yig'indisini
hisoblash. ning tekis massivi raqamlar elementlarni yoki prefiks summalarini saqlashi
mumkin. Birinchi holda, prefiks summalarini hisoblash chiziqli vaqtni talab
qiladi; ikkinchi holda, massiv elementlarini yangilash chiziqli vaqtni talab qiladi (har
ikkala holatda ham boshqa operatsiya doimiy vaqtda bajarilishi mumkin). Fenwick
daraxtlari ikkala operatsiyani ham bajarishga imkon beradi vaqt. Bunga
raqamlarni daraxt shaklida ifodalash orqali erishiladi 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 mumkin 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.
13

Fenwick daraxti yechimining asosiy g'oyasi har bir indeks uchun
javobgarlik oralig'i yig'indisini oldindan hisoblashdir. Keyin, Fenwickning
oldindan hisoblangan qiymatlari asosida indeksning prefiks yig'indisini
hisoblashimiz mumkin . Bundan tashqari, biz indeksdagi elementni
yangilaganimizda , biz faqat indeksni qamrab oladigan Fenwick oldindan
hisoblangan qiymatlarini yangilashimiz mumkin .
Ushbu Fenwick daraxti tuzilishida barg tugunlari indeks raqamlari
14

hisoblanadi. Har bir ichki tugun Fenwick qiymatini o'z ichiga oladi, uni o'z
farzandlari Fenwick qiymatlari va o'zining indeks qator raqamidan tuzish
mumkin.
Fenwick daraxti, shuningdek, Binary Indexed Tree deb ataladi yoki
shunchaki BIT qisqartiriladi.
Fenwick Tree deb ham ataladigan ikkilik indeksli daraxt massivdagi
samarali
hisoblash imkonini beradi. Masalan, massiv [2, 3, -1, 0, 6] uzunlikdagi 3
prefiksi [2, 3, -1] yig'indisi 2 + 3 + -1 = 4). Prefiks summalarini samarali
hisoblash turli stsenariylarda foydalidir. Keling, oddiy muammodan
boshlaylik.Bizga a[] massivi berilgan va biz u bilan ikki turdagi amallarni
bajara olishni xohlaymiz.i indeksida saqlangan qiymatni o'zgartiring. (Bu
nuqta yangilash operatsiyasi deb ataladi )
1.Uzunligi k bo‘lgan prefiksning yig‘indisini toping. (Bu diapazon yig'indisi
so'rovi deb ataladi )
Yuqoridagilarning to'g'ridan-to'g'ri amalga oshirilishi shunday ko'rinadi .
int a [] = { 2 , 1 , 4 , 6 , - 1 , 5 , - 32 , 0 , 1 };
void update ( int i , int v )
{
a [ i ] = v ;
}
int prefixsum ( int k )
{
int sum = 0 ;
for ( int i = 0 ; i < k ; i ++)
sum += a [ i ];
return sum ;
}
Bu mukammal yechim, lekin afsuski, prefiks yig'indisini hisoblash uchun
zarur bo'lgan vaqt massiv uzunligiga mutanosibdir, shuning uchun ko'p
sonli aralashgan operatsiyalar bajarilganda bu vaqt tugaydi.

15
Bundan yaxshiroq ish qila olamizmi? Albatta. Samarali yechimlardan biri
O(logN) vaqtida ikkala operatsiyani ham bajara oladigan segment
daraxtidan foydalanishdir.
Ikkilik indekslangan daraxtdan ham foydalanib, biz ikkala vazifani O(logN)
vaqtida bajarishimiz mumkin.
2.2. Fenwick daraxti dasturiy tahlili.
Ikkilik indeksli daraxtni tushunish uchun quyidagi masalani ko'rib chiqaylik.
Bizdaarr[0massivibor. . . n-1]. Biz 1 Birinchi i elementlarning yig'indisini
hisoblamoqchimiz . 2 arr[i] = x massivning belgilangan elementining qiymatini
o'zgartiring, bu erda 0 <= i <= n-1.
Oddiy yechim 0 dan i-1 gacha bo'lgan tsiklni bajarish va elementlarning
yig'indisini hisoblashdir. Qiymatni yangilash uchun arr[i] = x ni bajaring. Birinchi
operatsiya O(n) vaqtni oladi, ikkinchi operatsiya esa O(1) vaqtni oladi. Yana bir
oddiy yechim qo‘shimcha massiv yaratish va bu yangi massivda i-indeksdagi
birinchi i-chi elementlarning yig‘indisini saqlashdir. Berilgan diapazonning
yig'indisi endi O(1) vaqt ichida hisoblanishi mumkin, ammo yangilash jarayoni
hozir O(n) vaqtni oladi. Agar so'rov operatsiyalari ko'p bo'lsa, lekin yangilash
operatsiyalari juda oz bo'lsa, bu yaxshi ishlaydi.
O (log n) vaqtida so'rov va yangilash operatsiyalarini bajara
olamizmi? S amarali yechimlardan biri O(Logn) vaqtida ikkala operatsiyani
bajaradigan SegmentTree-dan foydalanishdir
. Muqobil yechim ikkilik indeksli daraxt bo'lib, u ikkala operatsiya uchun ham
O(Logn) vaqt murakkabligiga erishadi. Segment daraxti bilan solishtirganda,
Binary Indexed Tree kamroq joy talab qiladi va amalga oshirish osonroq.
Binary Indexed Tree massiv sifatida taqdim etiladi. Massiv BITree[]
bo‘lsin. Ikkilik indeksli daraxtning har bir tugunida kirish massivining ba'zi

elementlari yig'indisi saqlanadi. Ikkilik indeksli daraxtning o'lchami kirish
massivining o'lchamiga teng
16
bo'lib, n bilan belgilanadi. Quyidagi kodda biz amalga oshirish qulayligi uchun
n+1 o'lchamidan foydalanamiz.
Bu g‘oya barcha musbat sonlarni 2 ning darajalari yig‘indisi sifatida ifodalash
mumkinligiga asoslanadi. Masalan, 19 ni 16 + 2 + 1 sifatida ko‘rsatish mumkin.
BITree ning har bir tugunida n ta element yig‘indisi saqlanadi. 2 ning kuchi.
Masalan, yuqoridagi birinchi diagrammada (getSum() diagrammasi) dastlabki
12 ta elementning yig‘indisi oxirgi 4 ta elementning yig‘indisi (9 dan 12 gacha)
va 8 ning yig‘indisi bilan olinishi mumkin. elementlar (1 dan 8 gacha). n sonining
ikkilik ko'rinishidagi o'rnatilgan bitlar soni O(Logn) dir. Shuning uchun biz
getSum() va update() operatsiyalarida eng ko'p O(Logn) tugunlarini kesib
o'tamiz. Qurilishning vaqt murakkabligi O(nLogn) dir, chunki u barcha n element
uchun update() ni chaqiradi.
// Ikkilik indeks daraxtining amallarini ko'rsatish uchun C++ kod
#include <iostream>
using namespace std;
{ int sum = 0;
index = index + 1;
while (index>0)
{
sum += BITree[index];
index -= index & (-index);
}
return sum;
}
void updateBIT(int BITree[], int n, int index, int val){
index = index + 1;
while (index <= n)
{

$BITree[index] += val; index += index & (-index); 17 } } int *constructBITree(int arr[], int n) { int *BITree = new int[n+1]; for (int i=1; i<=n; i++) BITree[i] = 0; for (int i=0; i<n; i++) updateBIT(BITree, n, i, arr[i]); for (int i=1; i<=n; i++) cout << BITree[i] << " "; return BITree; } int main() { int A[] = {2, 1, 1, 3, 2, 3, 4, 5, 6, 7, 8, 9}; int n = sizeof(A)/sizeof(A[0]); int *BITree = constructBITree(A, n); cout << "Sum of elements in arr[0..5] is " << getSum(BITree, 5); A[3] += 6; updateBIT(BITree, n, 3, 6); cout << "\nYangilanishdan keyin arr[0..5] dagi elementlar yig indisi "ʻ << getSum(BITree, 5); return 0;} Ikkilik indeksli daraxt (Fenwick Tree) massivning prefiks yig'indisini tezda hisoblash uchun ishlatilishi mumkin bo'lgan samarali ma'lumotlar strukturasidir. Agar massivda mavjud qiymatlar o'zgaruvchan$

bo'lsa . m . e . qiymatlarni Fenwick daraxti yordamida o'zgartirish mumkin, bu juda
foydali. Odatda, agar biz
18
Ikkilik indeksli daraxt (Fenwick Tree) massivning prefiks yig'indisini tezda
hisoblash uchun ishlatilishi mumkin bo'lgan samarali ma'lumotlar
strukturasidir. Agar massivda mavjud qiymatlar o'zgaruvchan
bo'lsa . m . e . qiymatlarni Fenwick daraxti yordamida o'zgartirish mumkin, bu juda
foydali. Odatda, agar biz massivdagi 0 dan n gacha bo'lgan barcha
raqamlarning yig'indisini hisoblamoqchi bo'lsak, biz indeks-0 dan boshlab har
bir elementni ko'rib chiqamiz va indeks-n ga qadar barcha elementlarni
qo'shishni davom ettiramiz. Bu O(n) vaqtini oladi va o'lcham juda katta bo'lsa
va biz ko'p so'rovlarni bajarishimiz kerak bo'lganda samarali emas.Buning bir
yechimi prefiks sum massividan foydalanishdir. Prefiks yig'indisi massivi
oldindan hisoblangan massiv bo'lib, unda har qanday indeksdagi qiymat asl
massivdagi 0 dan ushbu indeksgacha bo'lgan barcha raqamlar yig'indisiga
teng bo'ladi. Agar bizdan x va y o'rtasidagi indekslarning umumiy yig'indisini
olishni so'ragan so'rovni olsak, biz x-1 indeksidagi prefiks summasini y
indeksidagi prefiks yig'indisidan ayirishimiz kerak, bu bizga x indekslaridagi
elementlarning yig'indisini beradi. y ga. Bu faqat 2 ta operatsiyani oladi va
shuning uchun biz O (1) vaqtida diapazon summasini olishimiz
mumkin. Ammo diqqatga sazovor narsa shundaki, agar indeksdagi
qiymat i o'zgarsa, kattaroq indekslar uchun barcha prefiks
summalari i o'zgaradi va bu O(N) vaqtini oladi.Xulosa qilib aytadigan bo'lsak,
birinchi yondashuv O(N) har qanday berilgan indekslar orasidagi barcha
elementlarning yig'indisini hisoblash uchun vaqt talab etadi, ammo O(1) har
qanday elementni yangilash uchun vaqt kerak bo'ladi. Prefiks yig'indisidan
foydalangan holda ikkinchi yondashuvda, O(1) har qanday berilgan indekslar
orasidagi barcha elementlarning yig'indisini hisoblash uchun vaqt kerak
bo'ladi, lekin O(N) agar dastlabki massivdagi biron bir element o'zgargan bo'lsa,
prefiks yig'indisi qatorini yangilash uchun vaqt kerak bo'ladi.Endi savol
shundaki, ikkalamiz o'rtasida muvozanat bo'lishi mumkinmi? ya'ni, har qanday
elementni yangilash vaqtida o'rtacha vaqt murakkabligi va prefiks summalarini
hisoblash uchun o'rtacha vaqt murakkabligi bormi? Ikkilik indeksli daraxt yoki
Fenwick daraxti bu savolning bir yechimidir .

ADABIYOTLAR RO’YXATI
1.Misty E Vermaat, Susan L Sebok, Steven M Freund. Discovering Computers
(C)2016 (2016 edition). Textbook.USA, 2016.
2.Mamarajabov M., Tursunov S. Kompyuter grafikasi va Web dizayn:
Darslik. T.: Cho‘lpon, 2013.
3.A.A. Xoidjigitov , Sh.f.Madraximov, U.E.Adamboyev “Informatika va
programmalash ” .O`quv qo`llanma, O`z.MU . 2005-yil.
4..B. Straustrop. “Yazik programmirovaniya C++. ” Binom press, 2006-yil.
5. Boltayev B.J , Azamatov A.R , Rahimov A.D “Algoritmlash va
dasturlash asoslari” kitobi
6.A.M. Po’latov “Algoritmlash va C++ dasturlash asoslari” kitobi
7. A.R. Azamatov “Algoritmlash asoslari” kitobi
1. https://library.ziyonet.uz/uz/book/126181
https://library.ziyonet.uz/uz/book/index?Book%5Blevel_id%5D=&Book
%5Btype_id%5D=1&Book%5Bcategory_id%5D=53&Book%5Btitle
%5D=&Book%5Bdescription%5D=&Book%5Blanguage_id%5D=&yt0=Qidiruv
20

ILOVALAR
ILOVA 1. Modul N1 boshlang’ich kodi.
class FenwickTree {
private : //xususiy
vector < int > data; //vector e’lon qilinyabdi
int getParent ( int i) const {//
return i - (i & ( - i)); //qiymatini qaytarayabdi
}
int getNext ( int i) const {
return i + (i & ( - i)); //qiymatini qaytarayabdi
}
public : //dasturning ixtiyoriy joyida ishlaydi
FenwickTree( int n) : data(n +1 , 0 ) {
}
int getSum( int i) const {
int sum = 0 ;//s=0 deb uzgaruvchi olayabmiz
++ i;
while (i > 0 ) {
sum += data[i];
i = getParent(i);
}
return sum;
}
void update( int i, int v) {
++ i;
while (i < data.size()) {// massiv o’lchamini olish
data[i] += v;
i = getNext(i);
}
}
};
21

Fenwick daraxti

Купить

Похожие документы
2001-yil sentabr voqealri va uning xalqaro munosabatlarga
1945-1990-yillarda Buyuk Britaniya
1918-1923 yillarda xalqaro munosabatlar, Versal Vashington siyetemasining tuzilishi
Ahmad al-farg‘oniy
Almashlab ekishni loyihalashtirish va joriy etish

Информация о документе

Продавец

Fenwick daraxti

Похожие документы