Fenvik daraxti va algoritmi
![Fenvik daraxti va algoritmi
1. MUNDARIJA
I. KIRISH ....................................................................................... 2
II. FENVIK DARAXTI VA ALGORITMI ................................................ 5
2.1 Fenvik daraxti haqida umumiy tushuncha ........................................................ 5
2.2 Fenvik daraxtining amaliyotda qo‘llanilishiga oid algoritmlar ...................... 10
2.2.1 Quyida Fenvik daraxtining ushbu vazifa uchun qo‘llash ........................................................... 10
2.2.2 Fenvik daraxti yordamida diapazon yig‘indisini hisoblash uchun dastur kodi ........................... 15
2.2.3 Fenvik daraxti yordamida eng katta ketma-ketlik muammosini maksimal darajada hal qilish
vazifasi ............................................................................................................................................... 19
2.3 Fenvik daraxt strukturasini yaratish bo‘yicha umumiy ko‘rsatmalar ............ 22
III. XULOSA ................................................................................... 23
IV. FOYDALANILGAN ADABIYOTLAR: ............................................. 26
4.1 Ijtimoiy sahifalar va saytlarda mavjud adabiyotlar: ...................................... 26
1](/data/documents/5ad0fb90-4f8a-47bc-a4d4-d9782c4d7c3a/page_1.png)
![KIRISH
Dasturlashda daraxtlar kodni tuzishda bo‘lgan muammolar va xatolar
yuzasidan yordam olish uchun ishlatiladi. Daraxtlar muhim funksiyalar va o‘zaro
bog‘lanishni ta’minlash uchun yaratilgan hamda dastur kodi oson yozilishi uchun
ishlatiladi. Hisoblashda ishlatiladigan daraxtlar grafik nazariyasidagi daraxtlarning
matematik konstruksiyalariga o‘xshash, ammo farq qilishi mumkin, to‘plamlar
nazariyasidagi daraxtlar va tavsiflovchi to‘plamlar nazariyasidagi daraxtlar. Daraxt
ma’lumotlar tuzilishi - bu ma’lumotlarni joylashtirish va qidirish oson bo‘lgan
tarzda ifodalash, hamda tartibga solish uchun ishlatiladigan ierarxik tuzilma. Bu
qirralar bilan bog‘langan va tugunlar o‘rtasida ierarxik munosabatlarga ega
bo‘lgan tugunlar to‘plamidir. Daraxtning eng yuqori tuguniga ildiz, uning
ostidagi tugunlarga esa avlod tugunlari deyiladi. Ushbu ma’lumotlar tuzilishi
kompyuterda ma’lumotlarni yanada samarali ishlatish uchun tartibga solish va
saqlashning maxsus usuli hisoblanadi. U qirralar orqali bog‘langan markaziy
tugun, strukturaviy tugunlar va pastki tugunlardan iborat. Shuni ham aytishimiz
mumkinki, daraxt ma’lumotlari tuzilishi bir-biri bilan bog‘langan ildizlar, novdalar
va barglarga ega. Har bir tugunda bir nechta avlod tugunlar bo‘lishi mumkin va
bu avlod tugunlari ham o‘zlarining avlod tugunlariga ega bo‘lib, rekursiv
tuzilmani hosil qiladi. Daraxtlar - bu dinamik to‘plam amallarni bajaradigan
ma’lumotlar tuzilmalari. Bunday amallar sifatida elementni qidirish,
minimal(maksimal) elementni qidirish, kiritish, o‘chirish, avlod-ajdodga o‘tish,
avlodga o‘tish kabilarni keltirish mumkin. Shunday qilib, daraxt oddiy lug‘at
sifatida ham, ustivor navbat sifatida ham ishlatilishi mumkin. Daraxtdagi
ma’lumotlar ketma-ket saqlanmaydi, ya’ni ular chiziqli saqlanmaydi, balki ular bir
necha darajalarda joylashtirilgan va biz buni iyerarxik tuzilma deb aytishimiz
mumkin. Shu sababli, daraxt chiziqli bo‘lmagan ma’lumotlar tuzilishi deb
hisoblanadi. Daraxt ma’lumotlar tuzilishiga extiyojlar: kompyuterdagi ma’lumotlar
tuzilmasi(fayllar tizimi)ni qurilishida ma’lumotlar joylashuvi daraxtlar asosida
2](/data/documents/5ad0fb90-4f8a-47bc-a4d4-d9782c4d7c3a/page_2.png)
![quriladi; kompilyator dizaynida dastur tuzilishini ifodalash uchun sintaksis daraxti
ishlatiladi; B daraxtlari va boshqa daraxt tuzilmalari ma’lumotlar bazasini
indekslashda ma’lumotlarni samarali qidirish va olish uchun ishlatiladi.
Daraxt ma’lumotlar tuzilishining afvzalliklari:
daraxtlar daraxt turiga qarab samarali qidirishni taklif qiladi, o‘rtacha
qidirish vaqtlari O(log n) bo‘lib, ushbu usul AVL kabi muvozanatli
daraxtlar uchundir;
daraxtlar ma’lumotlarning ierarxik ko‘rinishini ta’minlaydi, bu esa katta
hajmdagi ma’lumotlarni tartibga solish va boshqarishni osonlashtiradi;
daraxtlarning rekursiv tabiati ularni rekursiv algoritmlar yordamida o‘tish
va boshqarishni osonlashtiradi.
Daraxt ma’lumotlar tuzilishining kamchiliklari:
muvozanatsiz daraxtlar, ya’ni daraxtning balandligi bir tomonga qiyshaygan,
bu esa qidiruv vaqtlarining samarasizligiga olib kelishi mumkin;
daraxtlar massivlar va bog‘langan ro‘yxatlar kabi ba’zi boshqa ma’lumotlar
tuzilmalariga qaraganda ko‘proq xotira maydonini talab qiladi, ayniqsa
daraxt juda katta bo‘lsa;
daraxtlarni amalga oshirish va manipulyatsiya qilish murakkab bo‘lishi
mumkin va algoritmlarni yaxshi tushunishni talab qiladi.
Fenvik daraxti daraxtlarning indekslangan turi bo‘lib, dasturlashda
dasturchilarga kodni tuzishda yordam beradi va kodni tuzish va bajarishda
xatoliklar kamayadi. Fenvik daraxti dasturchilarga kodni yozishda kerakli sintaksis
va qoidalarni tushuntiradi va kodni to‘g‘ri yozishni osonlashtiradi. Bu qoidalarga
amal qilish orqali, dasturchilar kodni to‘g‘ri yozishni osonlashtiradi va kodni
tuzish va boshqa dasturlash vazifalarini bajarishda xatoliklar kamayadi. Fenvik
daraxti Python dasturlash tilida ham qo‘llaniladi. Bu daraxt Python dasturlash
tilida o‘zining sintaksisiga ega bo‘lib, dasturchilarga o‘zgaruvchan ma’lumotlar
saqlash va ularga murojaat qilish imkoniyatini beradi.
Fenvik daraxtining asosiy afvzalliklari quyidagilardan iborat:
3](/data/documents/5ad0fb90-4f8a-47bc-a4d4-d9782c4d7c3a/page_3.png)
![ o‘zgaruvchan va o‘zgarmas ma’lumotlar uchun xususiyatlarda;
sintaksisda; yorqinligida;
keng qo‘llanilishida; xavfsizligida; o‘ziga xos funksiyalarida;
keng tarqalganligida; yangilanishlarni kuzatib borish juda ham qulay.
Fenvik daraxtining asosiy kamchiliklari quyidagilardan iborat:
tezlik;
xotira sarflanishi;
qiyinchilik;
resurslar miqdorining cheklanganligi;
o‘zgaruvchilardan foydalanishning noqulayligi.
Dasturlashda Fenvik daraxtini o‘rganish juda ham zarur. Fenvik daraxti
dasturlashda matematik masalalarni yechish, algoritmlar yaratish va
ma’lumotlarni tahlil qilish uchun ishlatiladi. Shu tarzda, ishlab chiquvchilar
muhim muammolarni hal qilishlari va dasturlarning yaxshiroq va samarali
ishlashiga yordam berishlari mumkin. Fenvik daraxtida qo‘llaniluvchi
o‘zgaruvchilar Fenvik o‘zgaruvchilar deb ataladi va Fenvik o‘zgaruvchilari
dasturchilarga funksiya ichida aniqlanmagan va funksiyadan tashqarida
aniqlangan o‘zgaruvchilarga kirishga imkon beradi. Bu dasturchilarga funksiyalar
o‘rtasida ma’lumotlarni almashish va dasturning turli qismlari o‘rtasida
ma’lumotlarni uzatish imkonini beradi.
4](/data/documents/5ad0fb90-4f8a-47bc-a4d4-d9782c4d7c3a/page_4.png)
![FENVIK DARAXTI VA ALGORITMI
2.1 Fenvik daraxti haqida umumiy tushuncha
Fenvik daraxti dasturlashda o‘zining o‘ziga xos xususiyatlari bilan
ajratilgan. Bu xususiyatlar esa o‘zgaruvchan va o‘zgarmas bo‘lishi mumkin.
Fenvik daraxti (ingliz tilidan olingan bo‘lib, “ikkilik indeksli daraxt” degan
ma’noni anglatadi) – prefiks yig‘indisini samarali hisoblashi va elementlarni
yangilashi mumkin bo‘lgan ma’lumotlar tuzilishi, saqlashni talab qiladigan
ma’lumotlar tuzilishi O(n) o‘lchovli xotira va samarali hisoblangan quyidagi
operatsiyalarni bajarish kabi bir qancha vazifalarni bajaradi:
qatordagi istalgan elementning qiymatini osongina o‘zgartirish;
[i, j] segmentdagi assotsiativ, komutativ, qiymat qaytaradigan operatsiyani
bajarish(odatda bu yig‘indini hisoblovchi yig‘indi funksiyasi);
Ikkilik daraxtning barglarida asl massivning qiymatlari, qolgan tugunlarida
esa avlodlarning qiymatlari yig‘indisi saqlanadi. Fenvik daraxti yordamida har bir
butun sonni ikki daraja yig‘indisi sifatida ifodalash mumkin. Xuddi shu tarzda,
jami yig‘indini ushbu o‘zgaruvchan chastota to‘plamlari yig‘indisi sifatida
hisoblash mumkin.
Fenvik daraxtining strukturasi hamda unda yig‘indi funksiyasining
qo‘llanilishi quyidagicha:
vector<int> daraxt;
int size;
void increase(int index, int value)
{
for(int i=index; i<size; i = (i | (i+1)))
daraxt[i] += value;
}
int sum(int right)
5](/data/documents/5ad0fb90-4f8a-47bc-a4d4-d9782c4d7c3a/page_5.png)
![{
int result = 0;
for(int j = right; j>=0; j = (j&(j+1)) – 1)
result += daraxt[j];
return result;
}
Bu dasturda Fenvik daraxt(binary indexed tree, ikkilik indeksli daraxt)
nomli ma’lumotlar strukturasini ishlatilgan. Bu struktura massivdagi
elementlarning qiymatlarini saqlash uchun ishlatiladi va massivdagi
elementlarning qiymatlarini o‘zgartirish va ularning yig‘indisini hisoblash uchun
ham yaxshi natijalar beradi.
Dasturda daraxt nomli vector<int> e’lon qilingan, bu esa Fenvik daraxtni
saqlash uchun ishlatiladi. size esa massivning o‘lchamini ifodalaydi.
increase funksiyasi massivdagi bir elementning qiymatini o‘zgartirish
uchun ishlatiladi. Uning ikkita argumenti bor: index va value . index massivdagi
o‘zgartiriladigan elementning indeksini, value esa o‘zgartiriladigan qiymatni
ifodalaydi. Funksiya for sikli yordamida Fenvik daraxtini yangilaydi.
sum funksiyasi esa massivdagi bir nechta elementlarning yig‘indisini
hisoblash uchun ishlatiladi. Uning argumenti right massivdagi oxirgi elementning
indeksini ifodalaydi. Funksiya for sikli yordamida Fenvik daraxtini orqaga
yo‘naltirib, yig‘indini hisoblaydi va natijani qaytaradi.
Fenvik daraxti amalga oshirish oson, tez ishlaydi, lekin nazariy jihatdan
mutlaqo aniq bo‘lmagan ma’lumotlar tuzilishi hisoblanadi. Xuddi shu
murakkablikka qaramay, Fenvik daraxti segmentlar daraxtiga qaraganda ancha
tezroq ishlaydi. Murakkabligi O(logn) bo‘lishiga qaramay, Fenvik daraxti
segmentlar daraxtiga qaraganda ancha tezroq ishlaydi. Fenvik daraxti qo‘llanilishi
esa, dasturchilar tomonidan o‘zgaruvchan ma’lumotlar saqlash uchun ishlatiladi.
6](/data/documents/5ad0fb90-4f8a-47bc-a4d4-d9782c4d7c3a/page_6.png)
![Ushbu daraxt ma’lumot tuzilmasi birinchi marta Piter Fenvik tomonidan 1994-
yilda tasvirlangan. Fenvik daraxti o‘zining o‘ziga xos sintaksisiga ega bo‘lib, bu
sintaksis dasturchilarga o‘zgaruvchan ma’lumotlar saqlash va ularga murojaat
qilish imkoniyatini beradi. Fenvik daraxti yordamida dasturchilar o‘zgaruvchan
ma’lumotlar ustida turli amallar bajarishlari mumkin, masalan, ularga yangi
qiymatlar tayinlash, ulardan ma’lumot o‘qish, ulardan ma’lumot o‘chirish va
hokazo. Fenvik daraxti Python dasturlash tilida ham qo‘llaniladi. Bu daraxt
Python dasturlash tilida o‘zining sintaksisiga ega bo‘lib, dasturchilarga
o‘zgaruvchan ma’lumotlar saqlash va ularga murojaat qilish imkoniyatini beradi.
Fenvik daraxtining dasturlashda quyidagi afvzalliklari mavjud:
O‘zgaruvchan va o‘zgarmas ma’lumotlar uchun xususiyatlar: Fenvik
daraxti o‘zgaruvchan va o‘zgarmas ma’lumotlar uchun xususiyatlar bilan
ajratilgan.
Sintaksis: Fenvik daraxti o‘ziga xos sintaksisga ega bo‘lib, bu sintaksis
dasturchilarga o‘zgaruvchan ma’lumotlar saqlash va ularga murojaat qilish
imkoniyatini beradi.
Yorqinlik: Fenvik daraxti yorqin va sodda sintaksisga ega bo‘lib, bu
dasturchilar uchun o‘rganishni oson qiladi.
Keng qo‘llanilishi: Fenvik daraxti Python, C++, Java va boshqa ko‘plab
dasturlash tillarida qo‘llaniladi.
Xavfsizlik: Fenvik daraxti xavfsizlikni oshirish uchun yordam beradi.
Misol uchun, o‘zgaruvchan ma’lumotlar ustida amallar bajarishda
xatoliklar sodir bo‘lishi mumkin, ammo Fenvik daraxti xatoliklarni oldini
olish uchun xavfsizlikni oshirish imkoniyatini beradi.
O‘ziga xos funksiyalari: Fenvik daraxtli o‘zining o‘ziga xos funksiyalarga
ega bo‘lib, bu funksiyalar dasturchilarga o‘zgaruvchan ma’lumotlar ustida
turli amallar bajarish imkoniyatini beradi.
Yorliq: Fenvik daraxti yorliq yordamida dasturchilarga dastur yozishda
yordam beradi.
7](/data/documents/5ad0fb90-4f8a-47bc-a4d4-d9782c4d7c3a/page_7.png)
![ Keng tarqalgan: Fenvik daraxti ko‘plab dasturlash tillarida keng tarqalgan
bo‘lib, bu dasturchilarga o‘rganish va ishlatishda yordam beradi.
Fenvik o‘zgaruvchilar - bu funksiya ichida aniqlanmagan va funksiyadan
tashqarida aniqlangan o‘zgaruvchilar. Ushbu o‘zgaruvchilar dasturchilarga
funksiyalar o‘rtasida ma’lumotlarni almashish va dasturning turli qismlari
o‘rtasida ma’lumotlarni uzatish imkonini beradi.
Fenvik o‘zgaruvchilardan foydalanishning afzalliklari:
bu dasturchilarga funksiyalar o‘rtasida ma’lumotlarni almashish imkonini
beradi;
bu dasturning turli qismlari o‘rtasida ma’lumotlarni to‘g‘ri uzatishni
osonlashtiradi;
bu dasturchilarga kamroq kod yozish imkonini beradi.
Fenvik o‘zgaruvchilari dasturlashda juda muhimdir va chastota
o‘zgaruvchilari ushbu funksiyalarning ishlashiga ta’sir qilishi mumkin. Fenvik
o‘zgaruvchilar - bu funksiya ichida aniqlanmagan va funksiyadan tashqarida
aniqlangan o‘zgaruvchilar. Fenvik o‘zgaruvchilarining asosiy kamchiligi
shundaki, ular dasturning o‘qilishini sekinlashtiradi. Funksiya ichida
ishlatiladigan o‘zgaruvchining qayerdan kelib chiqqanligini tushunish qiyin
bo‘lishi mumkin, bu esa dasturni saqlashni qiyinlashtirishi mumkin. Bundan
tashqari, fenvik o‘zgaruvchilari dasturning aniqligiga ham ta’sir qilishi mumkin.
Masalan, agar funksiya ichida ishlatiladigan Fenvik o‘zgaruvchisi tasodifan
boshqa joyga o‘zgartirilsa, funksiya natijasi noto‘g‘ri bo‘lishi mumkin. Natijada,
dasturlash tilida fenvik o‘zgaruvchilaridan foydalanishni iloji boricha kamaytirish
kerak. Funksiyalarda ishlatiladigan o‘zgaruvchilar, iloji bo‘lsa, funksiya
parametrlari sifatida aniqlanishi kerak.
Fenvik daraxti yoki ikkilik indekslangan daraxt - ko‘p vazifalarda
segmentlar daraxtini almashtiradigan, lekin ayni paytda 3-4 baravar tezroq
8](/data/documents/5ad0fb90-4f8a-47bc-a4d4-d9782c4d7c3a/page_8.png)
![ishlaydigan, mavjud bo‘lgan minimal xotira miqdorini egallaydigan ma’lumotlar
tuzilishi tez hamda tartibli yoziladigan va katta miqdordagi ma’lumotlar osonroq
umumlashtiriladigan daraxt turi hisoblanadi. Ushbu struktura segmentlar
daraxtiga o‘xshaydi, ammo ushbu daraxt ma’lumotlar tuzilmasini tuzishni amalga
oshirish ancha oson hamda soddaroq. Fenvik daraxti ma’lumotlar tuzilishi
massivdagi daraxt bo‘lib, u quyidagi xususiyatlarga ega:
• har qanday [L; R] segmentidagi ba’zi qaytariladigan F operatsiyasining
qiymatini logarifmik vaqt ichida hisoblash imkonini beradi;
• har qanday elementning qiymatini O(logn)ga o‘zgartirishga imkon beradi;
• O(n) qiymatdagi xotirani talab qiladi;
F operatsiyasini turli yo‘llar bilan tanlash mumkin, lekin ko‘pincha interval
yig‘indisi operatsiyalari, interval mahsuloti, shuningdek ma’lum bir modifikatsiya
va cheklovlar, intervalda maksimal va minimalni topish yoki boshqa operatsiyalar
olinadi. A sosiylaridan biri shundaki, asl massivning bitta elementini
o‘zgartirganda, o‘rtacha O(n) qisman yig‘indilarni qayta hisoblash kerak va bu
vaqt talab etadi. Ushbu muammoni hal qilish uchun siz Fenvik daraxtidan
foydalanishingiz mumkin. Fenvik daraxlarining asosiy afzalligi uni tuzishning
osonligi va ma’lumot izlash so‘rovlarga javoblarning tezligi O(1)ga teng
bo‘lganligidadir.
9](/data/documents/5ad0fb90-4f8a-47bc-a4d4-d9782c4d7c3a/page_9.png)
![2.2 Fenvik daraxtining amaliyotda qo‘llanilishiga oid
algoritmlar
2.2.1 Quyida Fenvik daraxtining ushbu vazifa uchun qo‘llash
Tabiiy sonlarda aniqlangan va x&(x+1) (&- bit va) ga teng bo‘lgan g (x)
funksiyasini kiritamiz. Shunday qilib, g(x) = x, agar x ning ikkilik kengayishida
oxirgi 0 bo‘lsa (x/2). Va agar ikkilik kengayishda x kichik raqamlarda birliklar
guruhi mavjud bo‘lsa, unda funksiya x ga teng bo‘lib, oxirgi birliklar 0 ga
almashtiriladi.
Massiv berilsin A =[ a 0 , a 1 ,..., an − 1 ] . Biz massivni Fenvik daraxti deb ataymiz.
T daraxtdan n ta elementlar: T[i] =∑
k = F ( i ) i
ak , qayerda i = 0 .. n − 1 .. va F [ i ] - daraxt
ustida ishlash vaqtini tanlashga bog‘liq bo‘lgan ba’zi funktsiyalar. Vaqt o‘tishi
bilan elementni kiritish va o‘zgartirish operatsiyalarini bajarishga imkon
beradigan funktsiyalar mavjuddir. Murakkabligi - O ( logn ) ga teng. U oddiy
formula bilan berilgan: F [ i ]= i& ( i + 1 ) , qayerda & -bu bit mantiqiy operatsiya AND .
Qachon AND raqamlar va uning qiymatlari bittaga ko‘paytirilsa, biz bu raqamni
ketma-ket so‘nggi birliklarsiz olamiz.
Ushbu funksiyani boshqa formula bo‘yicha hisoblash mumkin:
F(i) = i – 2 h(i)
+1 , qayerda h(i) - raqamning ikkilik yozuvining oxirida ketma-
ket keladigan birliklar soni i . Ikkala variant ham tengdir, chunki ushbu
formulalardan biri tomonidan berilgan funktsiya raqam oxirida ketma-ket
keladigan barcha birliklarni nol bilan almashtiradi.
Dasturdagi ushbu funksiya kodi quyidagicha:
10](/data/documents/5ad0fb90-4f8a-47bc-a4d4-d9782c4d7c3a/page_10.png)
![const int N=100;
int t[N],a[N];
int sum(int L, int R)
{
int res=0;
while (R >= 0) {
res += t[R];
R = G( R ) - 1;
}
while (L >= 0) {
res -= t[L];
L = G(L) - 1;
}
return res;
}
Shuni ham ta’kidlash kerakki, har bir dastur uchun g (x) funksiyasi x ikkilik
yozuvidagi birliklar sonini kamida 1 ga kamaytiradi. Shundan kelib chiqadiki,
yig‘indini hisoblash O(log n) uchun amalga oshiriladi.
Elementlarni almashtirish quyidagicha:
Elementlarning qanday o‘zgarishiga qarab qisman yig‘indilarni tezda
o‘zgartirishni o‘rganishimiz kerak. Keyin biz massiv elementlarini o‘zgartirishimiz
kerak T[j], bunda ushbu tengsizlik o‘rinli bo‘ladi - G(j)<k<j. Barcha kerakli j lar
k[i] ketma-ketligiga tegishli bo‘ladi:
11](/data/documents/5ad0fb90-4f8a-47bc-a4d4-d9782c4d7c3a/page_11.png)
![Bu yerda bit tushuniladi:
Shuni ta’kidlash kerakki, bu funksiya qat’iy ravishda o‘sib boradi va eng
yomon holatda O(log) marta qo‘llaniladi, chunki u har safar k sonining ikkilik
kengayishida bitta birlikni qo‘shadi.
A[k] elementini d ga o‘zgartiradigan va shu bilan birga tegishli qisman
yig‘indilarni o‘zgartiradigan funksiyani yozamiz.
Dasturdagi ushbu funksiya kodi quyidagicha:
const int N=100;
int t[N],a[N];
void upd(int k, int d)
{
a[k]+=d;
while(k<N)
{
t[k]+=d;
k=(k|(k+1));
}
}
Bu Fenvik daraxtini berilgan qiymat bilan yangilaydigan C++ funksiyasi.
12](/data/documents/5ad0fb90-4f8a-47bc-a4d4-d9782c4d7c3a/page_12.png)
![Funksiya kirish sifatida ikkita butun sonni oladi, k va d, ular mos ravishda
yangilanadigan elementning indeksini va elementga qo‘shiladigan qiymatni
ifodalaydi. Funksiya avval a massividagi elementning qiymatini unga D qo‘shib
yangilaydi. Keyin Fenvik daraxtidagi tegishli tugunlarni vaqt sikli yordamida
daraxt ustida takrorlash orqali yangilaydi. Sikl k indeksidan boshlanadi va daraxt
bo‘ylab ildizga ko‘tariladi va yo‘l davomida har bir tugunni yangilaydi. Yangilash
qo‘shish orqali amalga oshiriladi d indeksdagi tugun qiymatiga k va keyin formula
yordamida ota tugunga o‘tish: k = (k | (k + 1)).
| operatorining ikkilik qismlarini birlashtirgan k|(k + 1) operatsiyasi eng
o‘ngdagi 0 bitni aylantiradi k 1 ga va | operatsiyasi natijada olingan ikkilik
raqamlarni birlashtiradi. Ushbu formula daraxtni berilgan indeksdan uning asosiy
indeksiga ko‘tarish uchun ishlatiladi.
Umuman olganda, ushbu funktsiya Fenvik daraxtini berilgan qiymat bilan
yangilash uchun ishlatiladi, bu raqamlar qatorida samarali so‘rovlar va
yangilanishlarni amalga oshirishga imkon beradi.
t[i] - barcha f(i) uchun a[j] yig‘indisi < = j < = i bo‘lgan holat.
sum funktsiyasi - a qatorining barcha elementlari bo‘ylab harakatlanadigan joyga t
qatori bo‘ylab harakatlanib, iloji boricha segmentlar bo‘ylab "sakrash" ni amalga
oshiradi.
Upd funktsiyasi teskari yo‘nalishda - indekslarni ko‘paytirish tomon siljiydi, t[j]
yig‘indisi qiymatlarini faqat kerakli pozitsiyalar uchun yangilaydi, ya’ni
f (j) <= i <= j bo‘lgan barcha j uchun. Shubhasiz , ikkala operatsiyaning tezligi F
funksiyasini tanlashga bog‘liq bo‘ladi.
Ishga tushurishda endi biz t qatorini dastlabki hisoblashda uni nol bilan
boshlash mumkinligini ta’kidlaymiz. Shundan so‘ng, biz n ta elementning har biri
uchun upd(i, a[i]) funksiyasidan foydalanamiz. Keyin dastlabki hisoblash O(n*log
n)ga teng vaqtni oladi, bu oddiy qismiy yig‘indilar bilan tavsiflangan algoritmga
qaraganda ko‘proq vaqtni oladi.
13](/data/documents/5ad0fb90-4f8a-47bc-a4d4-d9782c4d7c3a/page_13.png)
![Fenvik daraxtini segment daraxt ma’lumot tuzilmalari bilan taqqoslashda
uning afvzalliklari va kamchiliklari quyidagicha:
Afvzalliklari:
• yuqorida aytib o‘tilgan soddalik va tezlik;
• xotira O(n)ni oladi;
• Fenvik daraxti segmentlar daraxtiga qaraganda bir marta kamroq xotirani
doimiy ravishda egallaydi. Buning sababi shundaki, Fenvik daraxti faqat
ba’zi elementlar uchun operatsiya qiymatini saqlaydi va segmentlar daraxti
elementlarning o‘zini va operatsiyaning qisman natijalarini pastki
kesmalarda saqlaydi, shuning uchun u kamida ikki baravar ko‘p xotirani
oladi;
• Fenvik daraxtini amalga oshirish osonroq;
• Fenvik daraxti qurilayotgan segmentdagi operatsiya qaytarilishi kerak, ya’ni
segmentdagi minimal (maksimal kabi) bu daraxtni segment daraxtidan farqli
o‘laroq hisoblash mumkin emas. Ammo agar biz prefiksda minimal
miqdorni topishimiz kerak bo‘lsa, unda Fenvik daraxti bu vazifani bajaradi.
Bunday Fenvik daraxti massiv elementlarini kamaytirish operatsiyasini
qo‘llab-quvvatlaydi. Daraxtdagi minimalni qayta hisoblash prefiksdagi
minimum massivini yangilashdan ko‘ra tezroq
Kamchiliklari:
• funksiya ma’lumot qaytarishi kerak bo‘lgan ayrim holatlarda ma’lumotlar
topilmay qolishi mumkin, ya’ni bu daraxt minimal va maksimal darajada
hisoblay olmaydi (ba’zi ma’lumotlarni yo‘qotishimiz bo‘lgan holatlar
bundan mustasno).
14](/data/documents/5ad0fb90-4f8a-47bc-a4d4-d9782c4d7c3a/page_14.png)
![2.2.2 Fenvik daraxti yordamida diapazon yig‘indisini hisoblash uchun
dastur kodi
1-qadam: Prefiks yig‘indisi daraxtini yangilash.
void update(int ind,int num){
while(ind<v.size()){
v[ind]+=num;
ind+=(ind & -ind);
}
}
2-qadam: Prefiks yig‘indisi daraxtiga so‘rovlar.
int getsum(int ind)
{
int sum=0;
while(ind>0)
{
sum+=v[ind];
ind-=(ind & -ind);
}
return sum;
}
3-qadam: Daraxt qurish .
for(int i=0;i<n;i++)
{
int num;
15](/data/documents/5ad0fb90-4f8a-47bc-a4d4-d9782c4d7c3a/page_15.png)
![cin>>num;
update(i+1,num);
}
4-qadam: Diapazon miqdorini olish .
while(t--)
{
int l,r;
cin>>l>>r;
cout<<getsum(r)-getsum(l-1)<<endl;
}
Ikkilik indekslangan daraxtni amalga oshirish oson va chiziqli xotirani
egallaydi. So‘rov va yangilash jarayoni O(log n ) vaqtini oladi.
Fenvik daraxti yordamida prefikslarda past/yuqori darajalarni saqlash ham
mumkin, ammo bunday daraxtning qo‘llab-quvvatlanadigan operatsiyalar sezilarli
darajada cheklangan:
• prefiksdagi minimal / maksimal qiymatlarga ko‘ra, o‘zboshimchalik
segmentida qiymatni belgilash mumkin emas.
• faqat elementlarni kamaytirish (minimal qidirish uchun
daraxt)/kattalashtirish (maksimal qidirish uchun daraxt) mumkin.
Amalga oshirish yig‘indini topish uchun amalga oshirish bilan deyarli bir xil:
#include <bits/stdc++.h>
using namespace std;
int n;
int a[100000]; //Massiv e’loni
16](/data/documents/5ad0fb90-4f8a-47bc-a4d4-d9782c4d7c3a/page_16.png)
![int f[100000]; //Fenvik daraxti
int get_min(int x) {
int result = INT_MAX;
for (; x >= 0; x = (x & (x + 1)) - 1) {
result = min(result, f[x]);
}
return result;
}
void assign(int idx, int val) {
a[idx] = val;
for(; idx < n; idx |= idx + 1) {
f[idx] = min(f[idx], val);
}
}
int main() {
cin >> n;
for (int i = 0; i < n; i++){
f[i] = INT_MAX;
}
for (int i = 0; i < n; i++){
int t;
cin >> t;
assign(i, t);
}
return 0;
}
Bu Fenvik daraxti ma’lumotlar tuzilishini amalga oshiradigan C++ dasturi.
Fenvik daraxti, shuningdek, ikkilik indekslangan daraxt sifatida ham tanilgan, bu
17](/data/documents/5ad0fb90-4f8a-47bc-a4d4-d9782c4d7c3a/page_17.png)
![raqamlar qatori bo‘yicha samarali so‘rovlar va yangilanishlarni amalga oshirishga
imkon beradigan ma’lumotlar tuzilishi.
Dastur kerakli sarlavha fayllarini qo‘shish va ba’zi o‘zgaruvchilarni e’lon
qilish bilan boshlanadi. ’N’ o‘zgaruvchi massiv hajmini, `a` massivning o‘zi va `f``
esa Fenvik daraxtidir.
’Get_min’ funksiyasi massiv oralig‘idagi minimal qiymatni topish uchun
ishlatiladi. U oraliqdagi oxirgi element indeksini ifodalovchi kirish sifatida `x ’
butun sonni oladi. Keyin funktsiya `x` dan boshlab va orqaga qarab ildizga qarab
daraxt ustida takrorlanadi va duch kelgan minimal qiymatni qaytaradi.
’Assign’ funksiyasi massivdagi element qiymatini yangilash uchun
ishlatiladi. Kirish sifatida ikkita butun son olinadi, ’idx’ va ’val’, ular mos ravishda
yangilanadigan element indeksini va tayinlanadigan yangi qiymatni ifodalaydi.
Funksiya massivdagi elementning qiymatini yangilaydi va keyin Fenvik
daraxtidagi tegishli tugunlarni yangilaydi.
’Main’ funktsiyasi massiv hajmida o‘qiydi va Fenvik daraxtini `INT_MAX`
qiymatlari bilan boshlaydi. Keyin u massiv elementlarida o‘qiydi va ` assign `
funksiyasi yordamida Fenvik daraxtini mos ravishda yangilaydi.
18](/data/documents/5ad0fb90-4f8a-47bc-a4d4-d9782c4d7c3a/page_18.png)
![2.2.3 Fenvik daraxti yordamida eng katta ketma-ketlik muammosini
maksimal darajada hal qilish vazifasi
Yechish uchun ketma-ketlik elementlarini cheklash muhimdir. Agar a
i<= 10 6
,
keyin muammoni Fenvik daraxti yordamida hal qilish mumkin, aks holda avval
qiymatlarni "siqish" kerak.
Yechim g‘oyasi juda oddiy: qatorni qo‘llab-quvvatlab, chapdan o‘ngga
ketma-ket boramiz. Keyingi elementni qayta ishlashda biz u bilan tugaydigan
ketma-ketlikning uzunligini yaxshilashga harakat qilamiz. Buning uchun biz har
qanday qisqa uzunlikdagi ketma-ketlikni davom ettirishimiz yoki yangisini
boshlashimiz mumkin. Formula sifatida buni quyidagicha yozish mumkin (joriy
element x):
f[x]=max(f[x],maxi=0x−1f[i]+1)
Formulada maksimal prefiksga e’tibor bering. Agar siz uni Fenvik daraxti
bilan topsangiz murakkablik O(logn), muammoni hal qilish uchun murakkablik
O(nlogn)ga teng bo‘ladi. Formulada maksimal prefiksga e’tibor bering. Agar siz
uni Fenvik daraxti bilan topsangiz murakkablik O(logn), muammoni hal qilish
uchun murakkablik O(nlogn)ga teng bo‘ladi.
C++da amalga oshirish:
#include <bits/stdc++.h>
using namespace std;
int n;
int seq[100000];
int a[1000001];
int f[1000001];
int get_max(int x) {
int result = INT_MIN;
19](/data/documents/5ad0fb90-4f8a-47bc-a4d4-d9782c4d7c3a/page_19.png)
![for (; x >= 0; x = (x & (x + 1)) - 1) {
result = max(result, f[x]);
}
return result;
}
void assign(int idx, int val) {
a[idx] = val;
for(; idx <= 1000000; idx |= idx + 1) {
f[idx] = max(f[idx], val);
}
}
int main() {
cin >> n;
for(int i = 0; i < n; i++) {
cin >> seq[i];
}
for(int i = 0; i < n; i++) {
int x = seq[i];
int prev_max = get_max(x - 1);
if (prev_max + 1 > a[x]) {
assign(x, prev_max + 1);
}
}
int ans = get_max(1000000);
cout << ans << endl;
}
20](/data/documents/5ad0fb90-4f8a-47bc-a4d4-d9782c4d7c3a/page_20.png)
![Bu C++ dasturi, bir nechta sonlardan iborat bo‘lgan ketma-ketlikda eng uzun
o‘sishni topish uchun yozilgan. Dasturda, a va f nomli ikkita massiv ishlatiladi. a
massivi, ketma-ketlikdagi har bir sonni saqlaydi, f massivi esa, a massivida
berilgan indeksdagi sonni o‘z ichiga olgan eng katta sonni saqlaydi.
Dasturda, get_max funksiyasi, berilgan indeksdan boshlab orqaga qaytib,
f massivida eng katta sonni topadi. assign funksiyasi esa berilgan indeksdagi
qiymatni a massiviga yozadi va f massivida mos keladigan indekslarga eng katta
qiymatlarni yozadi.
Dasturda seq nomli massivga foydalanuvchi tomonidan sonlar kiritiladi.
Keyin har bir son uchun eng uzun o‘sishni topish uchun, get_max funksiyasi
yordamida avvalgi sonlardan eng katta sonni topib, keyin assign funksiyasi
yordamida eng uzun o‘sishni hisoblash uchun mos keladigan qiymatlarni a va f
massivlariga yozadi. Natijada, get_max funksiyasi yordamida eng katta sonni
topib, konsolga chiqaradi.
21](/data/documents/5ad0fb90-4f8a-47bc-a4d4-d9782c4d7c3a/page_21.png)
![2.3 Fenvik daraxt strukturasini yaratish bo‘yicha umumiy
ko‘rsatmalar
Fenvik daraxt strukturasi quyidagi bosqichlarda yaratiladi:
1. Massivdagi elementlar uchun Fenvik daraxt massivi yaratiladi. Fenvik
daraxt massivi, massivdagi elementlar sonidan bir necha bit ko‘p bo‘lgan
massivdir.
2. Fenvik daraxt massivining har bir elementi, massivdagi bir necha
elementning kumulyativ yig‘indisini saqlaydi.
3. Kumulyativ yig‘indini hisoblash uchun, Fenvik daraxt massivida bir necha
elementni qo‘shish kerak bo‘ladi. Bu elementlar, massivdagi elementlar
sonidan bir necha bit ko‘p bo‘lgan elementlar hisoblanadi
4. Kumulyativ yig‘indini hisoblash uchun, Fenvik daraxt massivida bir necha
elementni qo‘shish kerak bo‘ladi. Bu elementlar, massivdagi elementlar
sonidan bir necha bit ko‘p bo‘lgan elementlar hisoblanadi.
5. Kumulyativ yig‘indini hisoblash uchun, Fenvik daraxt massivida bir necha
elementni qo‘shish kerak bo‘ladi. Bu elementlar, massivdagi elementlar
sonidan bir necha bit ko‘p bo‘lgan elementlar hisoblanadi.
6. Fenvik daraxt massivida kumulyativ yig‘indini hisoblash uchun kerak
bo‘lgan barcha elementlar hisoblanadi.
Fenvik daraxt strukturasi massivdagi elementlar sonidan bir necha bit ko‘p
bo‘lgan holatlarda kumulyativ yig‘indinini tez hisoblash uchun juda samarali
hisoblanadi.
22](/data/documents/5ad0fb90-4f8a-47bc-a4d4-d9782c4d7c3a/page_22.png)
![XULOSA
Xulosa o‘rnida aytilsa, biz elementlarning yig‘indisi bo‘yicha so‘rovlarga
javob berishni va har qanday elementni logarifmik vaqt ichida o‘zgartirishni
o‘rgandik. Ushbu algoritmlar juda ko‘p foydalanishga ega va operatsiya natijasini
tezda o‘zgartirish va aniqlash kerak bo‘lgan barcha vazifalarda yordam berishi
mumkin. Ehtimol, ushbu tuzilmani qanday yozishni biladiganlarning to‘rtdan
biridan kamrog‘i uning qanday ishlashini to‘liq tushunishadi. Tahlil haqiqatan ham
juda murakkab bo‘lgani uchun mavhumlashtirish degan ishonchni qabul qilish
tavsiya etiladi. Fenvik daraxti bizning operatsiyamiz qaytarilganda, shuningdek
prefiks yig‘indisi hiylasi ishlaganda ishlatilishi mumkin. Fenvik daraxtini ishlatish
orqali massivdagi elementlarning yig‘indisini hisoblash va o‘zgartirish uchun
kerak bo‘lgan ma’lumotlarning xotiradan egallagan hajmini tejab qolish mumkin.
Shuningdek, Fenvik daraxtini ishlatish orqali massivdagi elementlarning
yig‘indisini hisoblash va o‘zgartirish uchun kerak bo‘lgan vaqtni ham kamaytirish
mumkin. Bu odatda xor moduli( | ) bo‘yicha yig‘indi, ko‘paytirish kabi oddiy
operatsiyalar (agar ushbu modulga hech narsa bo‘linmasligi kafolatlangan bo‘lsa)
bo‘lganda qo‘llaniladi. Fenvik daraxti(yoki binary indexed tree) nomli ma’lumotlar
strukturasini ishlatish orqali massivdagi elementlarning qiymatlarini saqlash,
o‘zgartirish va ularning yig‘indisini hisoblash mumkin. Bu struktura massivdagi
elementlarning qiymatlarini saqlash uchun juda kam xotira kerakligini ta’minlaydi
va shuningdek, massivdagi elementlarning yig‘indisini hisoblash uchun ham
yaxshi natijalar beradi. Fenvik daraxti massivdagi har bir elementni bir necha bitta
daraxtga bog‘lash orqali yaratiladi. Daraxtning har bir tugunida, tugunni o‘z ichiga
olgan elementlar yig‘indisi saqlanadi. Bu yig‘indilar daraxtning ajdod tugunlariga
qo‘shilgan holda massivdagi bir necha elementning yig‘indisini ifodalaydi.
Element qiymati o‘zgartirilganda, uni o‘z ichiga olgan daraxtdagi tugunlar ham
yangilangan hisoblanadi. Kumulativ yig‘indi – yig‘indini oshiruvchi yig‘indi.
Fenvik daraxti massivdagi qiymatlarning kumulativ yig‘indi va boshqa statistik
ma’lumotlarni tez hisoblash uchun ishlatiladi.
23](/data/documents/5ad0fb90-4f8a-47bc-a4d4-d9782c4d7c3a/page_23.png)
![Ushbu ma’lumotlar strukturasining amaliyotda bir nechta sohalari mavjud:
kumulativ yig‘indini hisoblash:
Fenvik daraxti massivdagi har bir elementning qiymatini o‘z ichiga olgan
daraxtdagi tugunlar yig‘indisi orqali hisoblaydi. Bu, massivdagi har qanday
elementning kumulativ yig‘indini tez hisoblash uchun yaxshi usuldir.
Massivdagi har qanday elementni o‘zgartirish: Fenvik daraxti massivdagi
har qanday elementni o‘zgartirish uchun ham ishlatiladi. Element qiymati
o‘zgartirilganda, uni o‘z ichiga olgan daraxtdagi tugunlar ham yangilangan
holda yana hisoblanadi.
Massivdagi har qanday elementni o‘qish: Fenvik daraxti massivdagi har
qanday elementning qiymatini o‘qish uchun ham ishlatiladi. Elementning
qiymati, uni o‘z ichiga olgan daraxtdagi tugunlar yig‘indisi orqali
hisoblanadi.
Bir necha elementning yig‘indisini hisoblash: Fenvik daraxti massivdagi bir
necha elementning yig‘indisini hisoblash uchun ham ishlatiladi. Bir necha
elementning yig‘indisi, ularning daraxtdagi tugunlar yig‘indisi orqali
hisoblanadi.
Fenvik daraxti amaliyotda katta ma’lumotlar to‘plamlarini ishlab chiqish,
statistik analizlar, matematik hisob-kitob va boshqa sohalarda ham ishlatiladi.
Masalan, Fenvik daraxti matritsa elementlarining yig‘indisini hisoblash uchun ham
ishlatiladi.
Fenvik daraxti amaliyotda tez va samarali hisob-kitob uchun juda muhimdir.
Ushbu ma’lumotlar strukturasining yordamida massivdagi har qanday elementni
o‘zgartirish, o‘qish va bir necha elementning yig‘indisini hisoblash uchun O(logn)
vaqt talab qilinadi.
Fenvik daraxt(yoki Binary Indexed Tree) ma’lumotlar strukturasini
ishlatmasangiz, siz ma’lumotlar yig‘indisini hisoblash uchun boshqa algoritmlar va
strukturalardan foydalanishingiz mumkin. Siz ma’lumotlar yig‘indisini hisoblash
uchun odatda "prefix sum" algoritmini ishlatasiz. Bu algoritm, bir massivning har
24](/data/documents/5ad0fb90-4f8a-47bc-a4d4-d9782c4d7c3a/page_24.png)
![bir elementining qiymatini o‘zidan oldingi elementning qiymati bilan qo‘shib
boradi. Bunday qilib, siz massivning har bir elementining kumulativ yig‘indisini
hisoblash uchun o‘zgaruvchilarni qo‘shib borishingiz mumkin.
Fenvik daraxtidan foydalanish o‘rnida Segment daraxt(yoki Interval Tree)
ma’lumotlar strukturasini ishlatish ham mumkin. Segment daraxti ma’lumotlar
yig‘indisini hisoblash uchun ham yaxshi ishlaydi va Fenvik daraxtidan
foydalanishdan boshqa variantlardan biridir. Boshqa algoritmlar va strukturalar
ham mavjud, shuningdek, siz ma’lumotlar yig‘indisini hisoblash uchun
o‘zgaruvchilarni qo‘shib borish yoki boshqa yordamchi strukturalardan
foydalanishingiz mumkin.
Fenvik daraxtini qo‘llashda uning muhimligi qay darajada ekanligini anglab
yetish zarur, chunki ushbu ma’lumot tuzilmasi ham boshqa ma’lumot tuzilmalari
kabi murakkab tuzilmagan bo‘lib, Fenvik daraxtini qo‘llash xatolardan holi emas.
Aslini olganda hech bir ma’lumot tuzilmasi murakkab tuzilmagan bo‘lib,
ma’lumotlar tuzilmalarining dasturda qo‘llanilishida yagona tuzilmadan
foydalanilmaydi. Bundan kelib chiqadiki, Fenvik daraxtini qo‘llashda ham, Fenvik
daraxti ma’lumotlar tuzilmasiga mos, hamda uning kamchiliklarini bartaraf etuvchi
ma’lumot tuzilmalari bilan mutanosib holatda qo‘llash tavsiya etiladi. Fenvik
daraxtining eng asosiy afvzalligi uning ma’lumotlarni saqlash tuzilmasini tashkil
qilishning nihoyatda sodda, ma’lumotlarga o‘zgartirish kiritish oson hamda qulay
hisoblanar ekan, uni qo‘shimcha tuzilmalar bilan birgalikda qo‘llay olish orqali
katta yutuqlarga erishish mumkin.
25](/data/documents/5ad0fb90-4f8a-47bc-a4d4-d9782c4d7c3a/page_25.png)
![FOYDALANILGAN ADABIYOTLAR:
4.1 Ijtimoiy sahifalar va saytlarda mavjud adabiyotlar:
- https://algorithmica.org/ru/fenwick ;
- https://habr.com/ru/articles/112828/ ;
- https://uz.zahn-info-portal.de/wiki/Fenwick_tree ;
- https://brestprog.by/topics/fenwicktree/ ;
- https://neerc.ifmo.ru/wiki/index.php?
title=Многомерное_дерево_Фенвика ;
- https://digitrain.ru/articles/244795/ ;
- https://ppt-online.org/949421 ;
- https://algoprog.ru/material/fenwick ;
- https://ru.algorithmica.org/cs/range-queries/fenwick/ ;
- https://neerc.ifmo.ru/wiki/index.php?title=Дерево_Фенвика ;
26](/data/documents/5ad0fb90-4f8a-47bc-a4d4-d9782c4d7c3a/page_26.png)
Fenvik daraxti va algoritmi 1. MUNDARIJA I. KIRISH ....................................................................................... 2 II. FENVIK DARAXTI VA ALGORITMI ................................................ 5 2.1 Fenvik daraxti haqida umumiy tushuncha ........................................................ 5 2.2 Fenvik daraxtining amaliyotda qo‘llanilishiga oid algoritmlar ...................... 10 2.2.1 Quyida Fenvik daraxtining ushbu vazifa uchun qo‘llash ........................................................... 10 2.2.2 Fenvik daraxti yordamida diapazon yig‘indisini hisoblash uchun dastur kodi ........................... 15 2.2.3 Fenvik daraxti yordamida eng katta ketma-ketlik muammosini maksimal darajada hal qilish vazifasi ............................................................................................................................................... 19 2.3 Fenvik daraxt strukturasini yaratish bo‘yicha umumiy ko‘rsatmalar ............ 22 III. XULOSA ................................................................................... 23 IV. FOYDALANILGAN ADABIYOTLAR: ............................................. 26 4.1 Ijtimoiy sahifalar va saytlarda mavjud adabiyotlar: ...................................... 26 1
KIRISH Dasturlashda daraxtlar kodni tuzishda bo‘lgan muammolar va xatolar yuzasidan yordam olish uchun ishlatiladi. Daraxtlar muhim funksiyalar va o‘zaro bog‘lanishni ta’minlash uchun yaratilgan hamda dastur kodi oson yozilishi uchun ishlatiladi. Hisoblashda ishlatiladigan daraxtlar grafik nazariyasidagi daraxtlarning matematik konstruksiyalariga o‘xshash, ammo farq qilishi mumkin, to‘plamlar nazariyasidagi daraxtlar va tavsiflovchi to‘plamlar nazariyasidagi daraxtlar. Daraxt ma’lumotlar tuzilishi - bu ma’lumotlarni joylashtirish va qidirish oson bo‘lgan tarzda ifodalash, hamda tartibga solish uchun ishlatiladigan ierarxik tuzilma. Bu qirralar bilan bog‘langan va tugunlar o‘rtasida ierarxik munosabatlarga ega bo‘lgan tugunlar to‘plamidir. Daraxtning eng yuqori tuguniga ildiz, uning ostidagi tugunlarga esa avlod tugunlari deyiladi. Ushbu ma’lumotlar tuzilishi kompyuterda ma’lumotlarni yanada samarali ishlatish uchun tartibga solish va saqlashning maxsus usuli hisoblanadi. U qirralar orqali bog‘langan markaziy tugun, strukturaviy tugunlar va pastki tugunlardan iborat. Shuni ham aytishimiz mumkinki, daraxt ma’lumotlari tuzilishi bir-biri bilan bog‘langan ildizlar, novdalar va barglarga ega. Har bir tugunda bir nechta avlod tugunlar bo‘lishi mumkin va bu avlod tugunlari ham o‘zlarining avlod tugunlariga ega bo‘lib, rekursiv tuzilmani hosil qiladi. Daraxtlar - bu dinamik to‘plam amallarni bajaradigan ma’lumotlar tuzilmalari. Bunday amallar sifatida elementni qidirish, minimal(maksimal) elementni qidirish, kiritish, o‘chirish, avlod-ajdodga o‘tish, avlodga o‘tish kabilarni keltirish mumkin. Shunday qilib, daraxt oddiy lug‘at sifatida ham, ustivor navbat sifatida ham ishlatilishi mumkin. Daraxtdagi ma’lumotlar ketma-ket saqlanmaydi, ya’ni ular chiziqli saqlanmaydi, balki ular bir necha darajalarda joylashtirilgan va biz buni iyerarxik tuzilma deb aytishimiz mumkin. Shu sababli, daraxt chiziqli bo‘lmagan ma’lumotlar tuzilishi deb hisoblanadi. Daraxt ma’lumotlar tuzilishiga extiyojlar: kompyuterdagi ma’lumotlar tuzilmasi(fayllar tizimi)ni qurilishida ma’lumotlar joylashuvi daraxtlar asosida 2
quriladi; kompilyator dizaynida dastur tuzilishini ifodalash uchun sintaksis daraxti ishlatiladi; B daraxtlari va boshqa daraxt tuzilmalari ma’lumotlar bazasini indekslashda ma’lumotlarni samarali qidirish va olish uchun ishlatiladi. Daraxt ma’lumotlar tuzilishining afvzalliklari: daraxtlar daraxt turiga qarab samarali qidirishni taklif qiladi, o‘rtacha qidirish vaqtlari O(log n) bo‘lib, ushbu usul AVL kabi muvozanatli daraxtlar uchundir; daraxtlar ma’lumotlarning ierarxik ko‘rinishini ta’minlaydi, bu esa katta hajmdagi ma’lumotlarni tartibga solish va boshqarishni osonlashtiradi; daraxtlarning rekursiv tabiati ularni rekursiv algoritmlar yordamida o‘tish va boshqarishni osonlashtiradi. Daraxt ma’lumotlar tuzilishining kamchiliklari: muvozanatsiz daraxtlar, ya’ni daraxtning balandligi bir tomonga qiyshaygan, bu esa qidiruv vaqtlarining samarasizligiga olib kelishi mumkin; daraxtlar massivlar va bog‘langan ro‘yxatlar kabi ba’zi boshqa ma’lumotlar tuzilmalariga qaraganda ko‘proq xotira maydonini talab qiladi, ayniqsa daraxt juda katta bo‘lsa; daraxtlarni amalga oshirish va manipulyatsiya qilish murakkab bo‘lishi mumkin va algoritmlarni yaxshi tushunishni talab qiladi. Fenvik daraxti daraxtlarning indekslangan turi bo‘lib, dasturlashda dasturchilarga kodni tuzishda yordam beradi va kodni tuzish va bajarishda xatoliklar kamayadi. Fenvik daraxti dasturchilarga kodni yozishda kerakli sintaksis va qoidalarni tushuntiradi va kodni to‘g‘ri yozishni osonlashtiradi. Bu qoidalarga amal qilish orqali, dasturchilar kodni to‘g‘ri yozishni osonlashtiradi va kodni tuzish va boshqa dasturlash vazifalarini bajarishda xatoliklar kamayadi. Fenvik daraxti Python dasturlash tilida ham qo‘llaniladi. Bu daraxt Python dasturlash tilida o‘zining sintaksisiga ega bo‘lib, dasturchilarga o‘zgaruvchan ma’lumotlar saqlash va ularga murojaat qilish imkoniyatini beradi. Fenvik daraxtining asosiy afvzalliklari quyidagilardan iborat: 3
o‘zgaruvchan va o‘zgarmas ma’lumotlar uchun xususiyatlarda; sintaksisda; yorqinligida; keng qo‘llanilishida; xavfsizligida; o‘ziga xos funksiyalarida; keng tarqalganligida; yangilanishlarni kuzatib borish juda ham qulay. Fenvik daraxtining asosiy kamchiliklari quyidagilardan iborat: tezlik; xotira sarflanishi; qiyinchilik; resurslar miqdorining cheklanganligi; o‘zgaruvchilardan foydalanishning noqulayligi. Dasturlashda Fenvik daraxtini o‘rganish juda ham zarur. Fenvik daraxti dasturlashda matematik masalalarni yechish, algoritmlar yaratish va ma’lumotlarni tahlil qilish uchun ishlatiladi. Shu tarzda, ishlab chiquvchilar muhim muammolarni hal qilishlari va dasturlarning yaxshiroq va samarali ishlashiga yordam berishlari mumkin. Fenvik daraxtida qo‘llaniluvchi o‘zgaruvchilar Fenvik o‘zgaruvchilar deb ataladi va Fenvik o‘zgaruvchilari dasturchilarga funksiya ichida aniqlanmagan va funksiyadan tashqarida aniqlangan o‘zgaruvchilarga kirishga imkon beradi. Bu dasturchilarga funksiyalar o‘rtasida ma’lumotlarni almashish va dasturning turli qismlari o‘rtasida ma’lumotlarni uzatish imkonini beradi. 4
FENVIK DARAXTI VA ALGORITMI 2.1 Fenvik daraxti haqida umumiy tushuncha Fenvik daraxti dasturlashda o‘zining o‘ziga xos xususiyatlari bilan ajratilgan. Bu xususiyatlar esa o‘zgaruvchan va o‘zgarmas bo‘lishi mumkin. Fenvik daraxti (ingliz tilidan olingan bo‘lib, “ikkilik indeksli daraxt” degan ma’noni anglatadi) – prefiks yig‘indisini samarali hisoblashi va elementlarni yangilashi mumkin bo‘lgan ma’lumotlar tuzilishi, saqlashni talab qiladigan ma’lumotlar tuzilishi O(n) o‘lchovli xotira va samarali hisoblangan quyidagi operatsiyalarni bajarish kabi bir qancha vazifalarni bajaradi: qatordagi istalgan elementning qiymatini osongina o‘zgartirish; [i, j] segmentdagi assotsiativ, komutativ, qiymat qaytaradigan operatsiyani bajarish(odatda bu yig‘indini hisoblovchi yig‘indi funksiyasi); Ikkilik daraxtning barglarida asl massivning qiymatlari, qolgan tugunlarida esa avlodlarning qiymatlari yig‘indisi saqlanadi. Fenvik daraxti yordamida har bir butun sonni ikki daraja yig‘indisi sifatida ifodalash mumkin. Xuddi shu tarzda, jami yig‘indini ushbu o‘zgaruvchan chastota to‘plamlari yig‘indisi sifatida hisoblash mumkin. Fenvik daraxtining strukturasi hamda unda yig‘indi funksiyasining qo‘llanilishi quyidagicha: vector<int> daraxt; int size; void increase(int index, int value) { for(int i=index; i<size; i = (i | (i+1))) daraxt[i] += value; } int sum(int right) 5