1. Algoritm — orınlawshı ushın málim bir máseleni sheshiwge qaratılǵan kórsetpelerdiń anıq izbe-izligi. Algoritmlar bul kompyuter programmaları artı daǵı ideyalar. Algoritm orınlawshısı

31) Binar indekslengen terek yaki fenevick algoritmi Ekilik indeksli terek yamasa Fenwick tereki Ekilik indeksli terekti túsiniw ushın tómendegi máseleni kórip shıǵayıq. Bizde arr[0 dızbeki bar... n-1]. Biz qáleymiz 1 Birinshi i elementlerdiń jıyındısın esaplań. 2 Dızbektiń belgilengen elementiniń ma`nisin ózgertiriń arr[i] = x bul erda 0 <= i <= n-1. Ápiwayı sheshim - 0 den i-1 ge shekem bolǵan cikldı jumısqa túsiriw hám elementlerdiń jıyındısın esaplaw. Bahanı jańalaw ushın arr[i] = x ni atqarıń. Birinshi operatsiya O (n) waqtın aladı, ekinshi operatsiya bolsa O (1) waqtın aladı.
Taǵı bir ápiwayı sheshim qosımsha dızbek jaratıw jáne bul jańa dızbekte i-indeks degi birinshi i -ne elementlerdiń jıyındısın saqlaw bolıp tabıladı. Berilgen diapazondıń jıyındısı endi O (1) waqıt ishinde esaplanıwı múmkin, biraq jańalaw procesi O (n) waqtın aladı. Eger soraw operatsiyaları kóp bolsa, lekin jańalaw operatsiyaları júdá az bolsa, bul jaqsı isleydi. O (log n) waqtında soraw hám jańalaw ámellerin atqara alamızba? Nátiyjeli sheshimlerden biri O (Logn) waqtında eki operatsiyanı atqaratuǵın Segment Tree-den paydalanıw bolıp tabıladı. Alternativ sheshim ekilik indeksli terek bolıp, ol eki operatsiya ushın da O (Logn) waqıt quramalılıǵına erisedi. Segment tereki menen salıstırǵanda, Ekilik indeksli terek kemrek jay talap etedi hám ámelge asırıw ańsatlaw. wákillik Ekilik indeksli terek dızbek retinde usınıs etiledi. Dızbek BITree[] bolsın. Ekilik indeksli terektiń hár bir túyininde kirisiw dızbekiniń birpara elementleri jıyındısı saqlanadı. Ekilik indeksli terektiń ólshemi kirisiw dızbekiniń ólshemine teń bolıp, n menen belgilenedi. Tómendegi kodta biz ámelge asırıw qolaylıǵı ushın n+1 ólsheminen paydalanamız. Qurılıs Biz BITree[] dagi barlıq bahalardı 0 retinde jumısqa túsiremiz. Keyin barlıq indeksler ushın update () ni shaqıramız, update () operatsiyası tómende talqılaw etiledi. Operatsiyalar GetSum (x): arr[0, …, x] kishi dızbektiń jıyındısın qaytaradı // arr[0..n-1] den dúzilgen BITree[0..n] járdeminde arr[0, …, x] kishi dızbekleri jıyındısın qaytaradı. 1) Shıǵıw summasın 0, ámeldegi indeksti x+1 retinde baslań. 2) Ámeldegi indeks 0 den úlken bolǵanda tómendegi ámellerdi atqarıń. …a) Jıyındına BITree[indeks] áskerg …b) BITree[indeks] ata-anasına ótiń. Ata-ananı alıp taslaw arqalı alıw múmkin ámeldegi indeksten aqırǵı ornatılǵan bıyt, yaǵnıy indeks = indeks - (indeks & (-index)) 3) Qaytıw summası. Jańalaw funktsiyası arr[i] ni óz ishine alǵan barlıq BITree túyinleri jańalanıwına isenim payda etiwi kerek. Biz BITree-dagi bunday túyinlerdi ámeldegi indekstiń aqırǵı ornaılǵan bitiga sáykes keletuǵın onlıq sannı qayta -qayta qosıw arqalı aylantıramız. Ekilik indeksli terek qanday isleydi? Bul ideya barlıq oń sanlardı 2 dıń dárejeleri jıyındısı retinde ańlatıw múmkinligine tiykarlanadı. Mısalı, 19 ni 16 + 2 + 1 retinde kórsetiw múmkin. BITree dıń hár bir túyininde n ta element jıyındısı saqlanadı, bul erda n - a 2 dıń kúshi. Mısalı, joqarıdaǵı birinshi diagrammada (getSum () diagramması ) dáslepki 12 elementtiń jıyındısı aqırǵı 4 element (9 dan 12 ge shekem) hám 8 teńiń jıyındısı menen alınıwı múmkin. elementler (1 den 8 ge shekem). n sanınıń ekilik kórinisindegi ornatılǵan bıytlar sanı O (Logn) bolıp tabıladı. Sol sebepli biz getSum () hám update () operatsiyalarında eń kóp O (Logn) túyinlerin kesip ótemiz. Qurılıstıń waqıt quramalılıǵı O (nLogn) bolıp tabıladı, sebebi ol barlıq n element ushın update () ni shaqıradı.