23. Floyda algoritmi

31. Binar indekslengen terek (Fenwick algorithm)
Binar indekslengen terek yamasa Fenwick teregi massivtiń dinamikalıq variantı bolıp tabıladı.
Ol massivte eki O(logn) waqıtlı ámeller qabıl etedi: aralıq sorawlardı esaplaw hám bahalardı jańalaw. Binar terektiń abzallıǵı sonda ol bizge nátiyjeli túrde massiv bahaların ózgertiw imkaniyatın beredi. Bunı massiv arqalı ámelge asırıp bolmaydı, sebebi hár bir update den keyin O(n) waqıt sarplap jańa massiv payda etiwge tuwra keledi.
Segment terek
Segment tree eki ámel qabıl etetuǵın maǵlıwmatlar strukturası bolıp tabıladı: aralıq sorawdı ámelge asırıw hám massiv ma`nisin update qılıw. Segment terekler jıyındı sorawı, minimum soraw, maksimum soraw hám sol sıyaqlı basqa sorawlardı qabıl etedi jáne bulardıń barlıǵında O(logn) waqıtlı eki ámelden paydalanadı. Binar indekslengen terekke salıstırılatuǵın bolsaq, segment terekti abzallıǵı sonda ol ulıwma struktura bolıp tabıladı. Binar indekslengen terek tek jıyındı sorawları ushın islese, segment terek basqa soraw túrlerin da óz ishine aladı. Biraq segment terek kóbirek yad talap etedi hám ámelge asırıw azmaz qıyınlaw.

32. Union-Find Algorithm
Yo'naltirilmagan grafikda cikl bar yamasa joq ekenligin tekseriw ushın Union-Find algoritmınan paydalanıw múmkin. Itibar beriń, biz cikldı anıqlaw algoritmın talqılaw etdik. Bul Union-Find-ga tiykarlanǵan taǵı bir usıl. Bul usıl grafikda óz-ózinen aylanıwlar joq ekenligin shama etedi.

C# kodi
// Naive implementation of find
static int find(int []parent, int i)
{
if (parent[i] == -1)
return i;
 
return find(parent, parent[i]);
}
 
// Naive implementation of union()
static void Union(int []parent, int x, int y)
{
int xset = find(parent, x);
int yset = find(parent, y);
parent[xset] = yset;
}
 
// This code is contributed by pratham76
Python dagi kodi
# Naive implementation of find
def find(parent, i):
 
if (parent[i] == -1):
return i
 
return find(parent, parent[i])
 
# Naive implementation of union()
def Union(parent, x, y):
 
xset = find(parent, x)
yset = find(parent, y)
parent[xset] = yset
 
# This code is contributed by rutvik_56

33. Quick Union Find algoritmi