###### tags: `ilo`, `map`

# Notatki - grupa zaawansowana

*MAP 2022*
## 19.02.2022
### Drzewo punkt-przedział
Drzewo sum z komentarzami

#include <iostream>
using namespace std;

// Potęga dwójki, która jest większa niż "n" w zadaniu
// 2^17 > 10^5, 2^20 > 10^6
const int TWO_EXP = 17;

const int BASE = 1<<TWO_EXP;
const int TREE_SIZE = BASE<<1;
int tree[TREE_SIZE];

void update(int x, int c)
{
    // Przejdź do odpowiedniego indeksu
    int xx = BASE + x;

    // Wstaw element c na pozycji x
    tree[xx] = c;

    // Przejdź do rodzica
    xx>>=1;

    // Wykonuj dopóki nie wyjdziesz poza drzewo
    // (Korzeń ma numer 1)
    while (xx > 0) {
        // Zaktualizuj wartość w wierzchołku
        // Wynik w wierzchołku to suma dzieci
        tree[xx] = tree[xx<<1] + tree[(xx<<1) + 1];

        // Przejdź do rodzica
        xx>>=1;
    }
}

// SPOSÓB 1. WYBIERAJ PRZEDZIAŁY BAZOWE OD GÓRY
// Zacznij od korzenia, który pokrywa cały przedział
int query(int a, int b, int v=1, int l=0, int r=BASE-1)
{
    // Sprawdź czy wierzchołek obsługuje przedział i zwróć dla niego wynik

    // Obsługiwany przedział jest poza szukanym
    if(r<a || l>b || r < l) return 0;

    // Obsługiwany przedział zawiera się cały w szukanym
    // Znaleźliśmy wierzchołek bazowy - zwróć wynik
    if(l>=a && r<=b) return tree[v];

    // Obsługiwany przedział jest za duży. Zleć zapytanie dzieciom
    int left = query(a, b, v<<1, l, (l+r)>>1);
    int right = query(a, b, (v<<1)+1, ((l+r)>>1)+1, r);

    return left + right;
}

// SPOSÓB 2. WYBIERAJ PRZEDZIAŁY BAZOWE OD DOŁU
int query2(int a, int b)
{
    int xa = BASE + a, xb = BASE + b;
    int suma = 0;

    // Dopóki lewa strzałka jest lewa i prawa jest prawa
    while(xa <= xb) {
        // Wierzchołek, który jest prawym dzieckiem na lewej ścieżce,
        // jest wierzchołkiem bazowym. Weź jego wynik i przesuń wskaźnik w prawo
        if (xa % 2 == 1) {
            suma += tree[xa];
            xa += 1;
        }
        // Symetrycznie dla wierzchołka na prawej ścieżce
        if (xb % 2 == 0) {
            suma += tree[xb];
            xb -= 1;
        }

        // Przejdź do rodziców
        xa >>= 1;
        xb >>= 1;
    }

    return suma;
}

// SPOSÓB 3. WYBIERAJ POD PRZEDZIAŁAMI BAZOWYMI
int query3(int a, int b)
{
    int xa = BASE + a, xb = BASE + b;
    int suma = 0;

    // Dodaj wyniki w liściach. Uważaj, by nie dodać dwa razy
    suma += tree[xa];
    if(xa != xb) suma += tree[xb];

    // Wykonuj dopóki lewy i prawy nie mają wspólnego rodzica
    while ((xa>>1) != (xb>>1)){
        // Sprawdź czy należy wziąć brata do wyniku.
        // W przypadku lewej ścieżki: znaleziono lewego syna na lewej ścieżce
        if (xa % 2 == 0)
            suma += tree[xa + 1];

        // Symetrycznie dla prawej ścieżki
        if (xb % 2 == 1)
            suma += tree[xb - 1];

        // Przejdź do rodziców
        xa >>= 1; xb >>= 1;
    }
    return suma;
}


int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, o, a, b;
    cin>>n;

    while(n--){
        cin>>o>>a>>b;

        if(o==1)
            update(b, a);
        else if(o==0){
            cout<<query3(a, b)<<'\n';
        }
    }


    return 0;
}

### Drzwo przedział-punkt
Update analogicznie do query z drzewa punkt-przedział.
Query analogicznie do update z drzewa punkt-przedział.

#include <iostream>
using namespace std;

const int TWO_EXP = 17;

const int BASE = 1 << TWO_EXP;
const int TREE_SIZE = BASE << 1;
int tree[TREE_SIZE];

int query(int x)
{
    int suma = 0;
    int xx = BASE + x;

    while (xx > 0)
    {
        suma += tree[xx];
        xx >>= 1;
    }

    return suma;
}

// SPOSÓB 1. PRZEDZIAŁY BAZOWE OD GÓRY
void update(int a, int b, int c, int v = 1, int l = 0, int r = BASE - 1)
{
    if (r < a || l > b || r < l)
        return;

    if (l >= a && r <= b){
        tree[v] += c;
        return;
    }

    update(a, b, c, v << 1, l, (l + r) >> 1);
    update(a, b, c, (v << 1) + 1, ((l + r) >> 1) + 1, r);
}

// SPOSÓB 2. PRZEDZIAŁY BAZOWE OD DOŁU
void update2(int a, int b, int c)
{
    int xa = BASE + a, xb = BASE + b;

    while (xa <= xb)
    {
        if (xa % 2 == 1)
        {
            tree[xa] += c;
            xa += 1;
        }

        if (xb % 2 == 0)
        {
            tree[xb] += c;
            xb -= 1;
        }

        xa >>= 1; xb >>= 1;
    }
}

// SPOSÓB 3. OD DOŁU INACZEJ
void update3(int a, int b, int c)
{
    int xa = BASE + a, xb = BASE + b;

    tree[xa] += c;
    if (xa != xb)
        tree[xb] += c;

    while ((xa >> 1) != (xb >> 1))
    {
        if (xa % 2 == 0)
            tree[xa + 1] += c;

        if (xb % 2 == 1)
            tree[xb - 1] += c;

        xa >>= 1; xb >>= 1;
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, o, a, b, c;
    cin >> n;

    while (n--)
    {
        cin >> o;

        if (o == 1){
            cin>>a>>b>>c;
            update3(a, b, c);
        }
        else if (o == 0) {
            cin>>a;
            cout << query(a) << '\n';
        }
    }

    return 0;
}

### Drzewo przedział-przedział
Dla zadania: [Drzewo przedziałowe](https://themis.ii.uni.wroc.pl/MAP1LO22_Z/ITREE)

#include <iostream>
using namespace std;

const int TWO_EXP = 20;

const int BASE = 1 << TWO_EXP;
const int TREE_SIZE = BASE << 1;
int tree[TREE_SIZE];
int lazy[TREE_SIZE];

void update_lazy(int l, int r, int v)
{
    // Wartość z lazy w wierzchołku v dodaj do lewego i prawego dziecka,
    // a następnie zepchnij lazy v do lazy dzieci i wyzeruj lazy v

    tree[l] = max(tree[l] + lazy[v], 0);
    tree[r] = max(tree[r] + lazy[v], 0);
    lazy[l] += lazy[v];
    lazy[r] += lazy[v];
    lazy[v] = 0;
}

void update(
    int a, int b, int value,
    int v=1, int l=0, int r=BASE-1
)
{
    // Jeśli wierzchołek nie mieści się w pytanym przedziale, anuluj
    if(r<a || l>b || r<l) return;

    // Jeśli obsługiwany przedział cały mieści się w zapytaniu,
    // to zaktualizuj wartość w wierzchołku i dodaj do lazy
    if(l >= a && r <= b){
        tree[v] += value;
        tree[v] = max(tree[v], 0);
        lazy[v] += value;
        return;
    }

    int vl = v<<1;
    int vr = vl + 1;
    int mid = (l + r)>>1;

    // zaktualizuj lazy
    update_lazy(vl, vr, v);

    // Zleć zapytanie do dzieci
    update(a, b, value, vl, l, mid);
    update(a, b, value, vr, mid + 1, r);

    // Zaktualizuj wartość w v
    tree[v] = max(tree[vl], tree[vr]);
}

int query(int a, int b, int v=1, int l=0, int r=BASE-1)
{
    if(r < a || l > b) return 0;

    if(l >= a && r <= b)
        return tree[v];

    int vl = v<<1;
    int vr = vl+1;
    int mid = (l+r)>>1;

    update_lazy(vl, vr, v);

    return max(
        query(a, b, vl, l, mid),
        query(a, b, vr, mid + 1, r)
    );
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, o, a, b, c;
    cin >> n;

    while (n--)
    {
        cin >> o;

        if (o == 1)
        {
            cin >> a >> b;
            update(a, b, 1);
        }
        else if (o == 2)
        {
            cin >> a >> b;
            update(a, b, -1);
        }
        else if (o == 0)
        {
            cout<<query(0, BASE-1)<<'\n';
        }
    }

    return 0;
}

---

*MAP 2021*
## 12.06.2021
### Drzewa
<!-- :::danger -->
**Definicja 1.** Graf posiada **cykl** jeżeli istnieją jakieś dwa wierzchołki $u$, $v$ takie, że z $u$ do $v$ można przejść na więcej niż jeden sposób (nie cofając się po krawędziach).
<!-- ::: -->
<!-- :::info -->
Intuicyjnie, cykl to po prostu "pętla" wierzchołków w grafie.
<!-- ::: -->

<!-- :::danger -->
**Definicja 2. Drzewo** to spójny graf acykliczny (nie posiadający cyklu).
<!-- ::: -->

<!-- :::info -->

graph G {
  // rankdir=LR
  // rank = same
  // layout=dot
	subgraph clusterA{
		pencolor=white
		node [shape=circle];
		1 -- 2;
		1 -- 3;
		3 -- 4;
		3 -- 5;
		labelloc=b;
		label="Przykład drzewa";
	}

	subgraph clusterB {
		pencolor=white
		node [shape=circle];
		6 [label="1"];
		labelloc=b;
		label="Drzewo jednowierzchołkowe"
	}

	subgraph clusterC {
		pencolor=white;
		node[shape=circle];
		7 [label="1"]
		8 [label="2"]
		9 [label="3"]
		7 -- {8, 9}
		{rank=same; 8 -- 9}
		labelloc=b
		label="To nie jest drzewo"
	}
	label="Rysunek 1. Przykłady drzew."
}

<!-- ::: -->
---

<!-- :::info -->
Drzewa często pojawiały się już na zajęciach pod postacią drzewa wywołań rekurencyjnych (np. w zadaniu _Hetmany_), czy trochę bardziej ukryte drzewo "zaznaczane" przez algorytm **DFS**:

graph G {
node [shape=circle]
	1 -- 2 	[color="red", style="bold"]
	2 -- 3	[color="red", style="bold"]
	2 -- 4	[color="red", style="bold"]
	{rank = "same"; 3 -- 4 [style="dashed"; color="blue"]}
	1 -- 5	[color="red", style="bold"]
	5 -- 6	[color="red", style="bold"]
	6 -- 7	[color="red", style="bold"]
	6 -- 8	[color="red", style="bold"]
	6 -- 9	[color="red", style="bold"]
	5 -- 9 	[style="dashed", color="blue"]
	1 -- 7 	[style="dashed", color="blue"]
	
	label="Rysunek 2. Przykład przejścia algorytmu DFS po drzewie.\nCzerwone krawędzie to te, po których przejdziemy w algorytmie DFS,\n niebieskie to te, po których algorytm nie przejdzie. Czerwone krawędzie\nwyznaczają drzewo."
}

**Definicja 3. Liściem** w drzewie nazywamy każdy wierzchołek stopnia $1$. Bardziej matematycznie: wierzchołek $v$ jest **liściem** $\iff \deg{v} = 1$.

**Twierdzenie 4.** Liczba krawędzi $N$-wierzchołkowego drzewa wynosi dokładnie $N - 1$.
**Dowód:** Dowód przeprowadzimy przy pomocy indukcji matematycznej, ważnej metody w dowodzeniu wielu twierdzeń, nie tylko dotyczących drzew.

Pokażemy najpierw, że teza jest prawdziwa dla $N = 1$. W zasadzie, to nie mamy czego pokazywać - takie drzewo jest tylko jedno, nie ma w ogóle krawędzi, zatem teza jest prawdziwa, gdyż $N - 1 = 1 - 1 = 0$.

Załóżmy teraz, że teza jest prawdziwa dla wszystkich drzew $N$-wierzchołkowych. Pokażemy, że każde $N+1$ wierzchołkowe drzewo ma w takim razie dokładnie $N$ krawędzi.

Wybierzmy dowolne $N+1$ wierzchołkowe drzewo. **Każde drzewo ma co najmniej jednego liścia (dlaczego?)**. Wyobraźmy sobie teraz, że wyrzucamy tego liścia z naszego drzewa. Dostajemy w takim razie drzewo, które ma $N$ wierzchołków. Założyliśmy, że teza zachodzi dla wszystkich $N$ wierzchołkowych drzew, zatem nasze drzewo ma dokładnie $N-1$ krawędzi. Przypomnijmy sobie teraz o wyrzuconym przez nas liściu i dołóżmy go z powrotem do naszego drzewa. Skoro to był liść, to znaczy, że wraz z nim dołożyliśmy dokładnie jedną krawędź. W takim razie krawędzi jest teraz $N - 1 + 1 = N$, co potwierdza naszą tezę.
<!-- $$\tag*{$\blacksquare$}$$ -->

<a name="rys3"></a>

graph G {
	node [shape="circle"]
	1--2
	1--3
	3--4
	3--5
	3--6 [style="dashed", color="red"]
	2--7
	6 [color="red"]
	label="Rysunek 3. Przykładowy rysunek obrazujący dowód dla pewnego 7-wierzchołkowego grafu.\n W \"czarnym\" grafie, z założenia mamy dokładnie 5 krawędzi. Po dołożeniu czerwonego\n wierzchołka i czerwonej krawędzi wracamy do pierwotnego grafu, dla którego teza\nrównież zachodzi."
}

Pokazaliśmy w tym momencie dowodzie rzeczy:
- teza zachodzi dla $N = 1$,
- jeżeli teza zachodzi dla pewnego $N$, to zachodzi dla $N + 1$.

To wystarczy, żeby udowodnić prawdziwość tezy dla dowolnego $N\in\mathbb{N}$. Skoro teza zachodzi dla $N = 1$, to z drugiego punktu zachodzi dla $N = 2$. Ale w takim razie zachodzi też dla $N = 3$ (znowu korzystając z drugiego punktu), więc zachodzi też dla $N = 4$, itd.
\begin{align}
''1 \Rightarrow 2 \Rightarrow 3 \Rightarrow 4 \Rightarrow 5 \Rightarrow \ldots''
\end{align}

Indukcja po rozmiarze drzewa jest bardzo częstą i użyteczną metodą dowodzenia własności drzew. Będzie się jeszcze pojawiać w przyszłości, dlatego zachęcam do próby dokładnego zrozumienia powyższego dowodu.

<!-- ::: -->
---

Bardzo często i wygodnie będzie nam wyróżniać jeden wierzchołek drzewa. Taki wyróżniony wierzchołek nazywamy **korzeniem** drzewa. Najczęściej drzewa rysujemy z korzeniem u szczytu i z wierzchołkami spadającymi w dół.

#### Od tego momentu zakładamy, że każde roważane przez nas drzewo jest ukorzenione.

**Fakt 4.** W drzewie, z każdego wierzchołka do każdego innego istnieje dokładnie jedna ścieżka.

To twierdzenie również można udowodnić indukcyjnie. Zachęcam Was do samodzielnego spróbowania.

**Definicja 5.** **Ojcem** wierzchołka $v$ w ukorzenionym drzewie jest pierwszy wierzchołek "nad" nim na ścieżce od $v$ do korzenia. Analogicznie definiujemy kolejne pojęcie: **synem** wierzchołka $v$ są wszystkie wierzchołki, dla których jest on ojcem.

Na [rysunku 3](#rys3) ojcem wierzchołka $3$ jest wierzchołek $1$, a jego synami są wierzchołki $4, 5, 6$.

**Definicja 6.** Wierzchołek $u$ jest **Przodkiem** wierzchołka $v$, jeżeli $u$ jest ojcem $v$ lub $u$ jest przodkiem ojca $v$ (czyli ojcem ojca ojca... ojca $v$). Mówimy, że $v$ jest **potomkiem** $u$ kiedy $u$ jest potomkiem $v$.

Zauważ, że przodkowie wierzchołka to wszystkie wierzchołki leżące na ścieżce od tego wierzchołka do korzenia.

**Definicja 7.** W ukorzenionym dzrzewie, **poddrzewem** wierzchołka $v$ nazwiemy graf złożony z wierzchołka $v$ i wszystkich jego potomków.

graph G {
	node [shape="circle"]
	1 -- 2
	2 -- 5
	5 -- 6 [color="red"]
	5 -- 7 [color="red"]
	1 -- 8
	8 -- 9
	2 -- 10
	5 -- 11 [color="red"]
	7 -- 3	[color="red"]
	7 -- 4	[color="red"]
	9 -- 12
	5 [color="red"]
	6 [color="red"]
	7 [color="red"]
	11 [color="red"]
	4 [color="red"]
	3 [color="red"]
	
	label="Rysunek 4. Czerwonym kolorem zostało oznaczone poddrzewo wierzchołka 5."
}

## 29.05.2021
### Przeszukiwanie w głąb (DFS)

void DFS(int v)
{
    // Zaznaczamy, że wierzchołek został odwiedzony 
    odw[v]=true;
    
    // Przeszukujemy jego sąsiadów
    for(int i=0; i<G[v].size(); i++)
    {
        int sasiad = G[v][i];
        
        // Jeśli sąsiad nieodwiedzony, to odwiedzamy
        if(!odw[sasiad])
        {
            DFS(sasiad);
        }

    }
    // i tyle :)
}

### Tablica
https://miro.com/app/board/o9J_lBtFzrk=/
<iframe width="768" height="432" src="https://miro.com/app/live-embed/o9J_lBtFzrk=/?moveToViewport=-770,-383,3395,1664" frameBorder="0" scrolling="no" allowFullScreen></iframe>

## 15.05.2021
### Reprezentacja grafu
#### Lista sąsiedztwa

//n=5
vector<int>G[5];

// 1 → 2
G[1].push_back(2);

// 2 → 3
G[2].push_back(3);

G[2].push_back(4);
G[4].push_back(2);

/* Lista sąsiedztwa:
 * 1 : 2
 * 2 : 3 4
 * 3 : 
 * 4 : 2
 *
*/
 
//Wypisujemy sąsiadów 2ki
for(int i=0; i<G[2].size(); i++){
    cout<<G[2][i]<<" ";
}

### Stopień wierzchołka
Liczba sąsiadów tego wierzchołka.
W macierzy sąsiedztwa trzeba przejrzeć cały wiersz, by obliczyć stopień, w liście sąsiedztwa natomiast wystarczy sprawdzić długość listy.

//stopień wierzchołka 2ego
G[2].size();

### Przeszukiwanie wszerz (BFS)
Odwiedzamy wierzchołki w kolejności ich odległości od wierzchołka stratowego.

// nax 100 wierzchołków
vector <int> G[101]; //graf w reprezentacji listy sąsiedztwa
bool odw[101]; //tablica odwiedzonych (wyzerowana), nikt nie odwiedzony
int odl[101]; //tablica odległości
queue<int>K; //co następne do przejrzenia

//zacznijmy od wierzchołka o numerze 0
K.push(0);

odw[0] = true; //odwiedzę wierzchołek 0

//przeglądamy, tak długo jak jest coś do przejrzenia
while(!K.empty()){
    int v = K.front(); //wierzchołek z początku kolejki
    K.pop(); //jak go zapisałem to go wyrzucam
    
    //pętla przeglądająca wszystkich sąsiadów wierzchołka v
    for(int i=0; i<G[v].size(); i++){
        int sasiad = G[v][i];
        
        if(!odw[sasiad]){
            K.push(sasiad);
            odl[sasiad] = odl[v] + 1;
            odw[sasiad] = true;
        }
    }
}

### Tablica
https://miro.com/app/board/o9J_lET9ebM=/
<iframe width="768" height="432" src="https://miro.com/app/live-embed/o9J_lET9ebM=/?moveToViewport=-1715,1749,1535,749" frameBorder="0" scrolling="no" allowFullScreen></iframe>

## 07.05.2021
### Graf
#### Pojęcia
- __wierzchołki__
- __krawędzie__, drogi, połączenie
- krawędzie mogą być __skierowane__ → (jednokierunkowe) lub __nieskierowane__ - (dwukierunkowe)
- wierzchołki do których możemy dotrzeć (zwykle bezpośrednio) z jakiegoś wierzchołka nazywamy jego __sąsiadami__

### Reprezentacja grafu
#### Macierz sąsiedztwa
W tablicy zaznaczamy, które wierzchołki (wiersze) są połączone z innymi (kolumny).

---

### Przykład implementacji vectora

...
#include <vector>

vector< int > w;

int main(){
    w.size(); // 0

    w.push_back(3); // [3]
    w.size(); // 1
    w.push_back(4); // [3, 4]
    w.size(); // 2
    w[0] = 17; // [17, 4]
    w[5] = 9; // ŹLE! BRAK TAKIEGO INDEKSU
    
    for(int i=0; i<w.size(); i++)
    {
        cout<<w[i]<<" ";
    }

return 0;
}

### Zadanie
Napisz program, który zapisuje do vectora liczby od 1 do n.

#include <iostream>
#include <vector>
using namespace std;

vector<int> wek;

int main(){
int n;
cin>>n;

for(int i=1; i<=n;i++)
{
    wek.push_back(i);
}

return 0;

### Tablica
https://miro.com/app/board/o9J_lF40y20=/
<iframe width="768" height="432" src="https://miro.com/app/live-embed/o9J_lF40y20=/?moveToViewport=-824,2959,1092,533" frameBorder="0" scrolling="no" allowFullScreen></iframe>