# Segment Tree — Guida e Plote

## Cfare eshte nje Segment Tree?

Imagjino qe je menaxher i nje zinxhiri dyqanesh me **1000 degë** ne Kosove. Cdo dite, ti ke nevoje te dish:

- "Sa eshte shitja totale nga dega 50 deri ne degen 200?"
- "Dega 75 ka bere sot 500€ — update-o!"

Me nje **liste te thjeshte** (array), per te mbledh shitjet e 150 degeve, duhet ti kalosh nje nga nje — **ngadalesht**.

Me nje **Segment Tree**, e merr pergjigjen menjehere — pa pasur nevoje te kalosh cdo dege.

> **Segment Tree** = nje peme binare qe ndan array-in ne segmente, ku secila nyje mban nje pergjigje te pergatitur (shume, minimum, maksimum, etj.) per nje pjese te array-it.

---

## Problemi real — pse na duhet?

Le te themi se kemi shitjet ditore per 8 dege:

```
Dega:    0    1    2    3    4    5    6    7
Shitja: 10€  25€  15€  30€  20€  45€  35€  50€
```

### Pyetja: "Sa jane shitjet totale nga dega 2 deri ne degen 5?"

**Pa Segment Tree (array i thjeshte):**
```
Shko te dega 2 → 15€
Shko te dega 3 → 30€
Shko te dega 4 → 20€
Shko te dega 5 → 45€
Mblidhi: 15 + 30 + 20 + 45 = 110€
```
Kjo kerkon **4 hapa**. Me 1 milion dege, mund te kerkoje 1 milion hapa per nje pyetje te vetme!

**Me Segment Tree:** Vetem **3 hapa**, pavaresisht sa dege ke.

---

## Si ndertohet — hap pas hapi

### Hapi 1: Fillo me array-in

```
[10, 25, 15, 30, 20, 45, 35, 50]
```

### Hapi 2: Nderto pemen nga poshte lart

Cdo **gjeth** (nyje e fundit) = nje element i array-it.
Cdo **nyje prind** = shuma e femijeve te saj.

```
                        [230]                    ← shuma totale (0-7)
                    /            \
              [80]                  [150]         ← (0-3) dhe (4-7)
            /      \              /      \
        [35]       [45]       [65]       [85]     ← (0-1), (2-3), (4-5), (6-7)
        / \        / \        / \        / \
      10   25    15   30    20   45    35   50    ← elementet origjinale
```

**Si lexohet:**
- Nyja `[35]` mban shumen e degeve 0 dhe 1 → `10 + 25 = 35`
- Nyja `[150]` mban shumen e degeve 4 deri 7 → `20 + 45 + 35 + 50 = 150`
- Rrenja `[230]` = shuma e te gjitha degeve

---

## Operacioni 1: Query (Pyetja)

### Shembull: "Sa jane shitjet e degeve 2–5?"

Pema shkon nga lart poshte dhe zgjedh vetem nyjet qe i duhen:

```
                        [230]          ← mbullon 0-7 (shume e gjere, zbrit)
                    /            \
              [80]                  [150]
            /      \              /      \
        [35]      >[45]<       >[65]<     [85]
        / \        / \          / \        / \
      10   25    15   30      20   45    35   50
                 ^^^  ^^^    ^^^  ^^^
                 dega dega   dega dega
                  2    3      4    5
```

**Hapat:**
1. Nyja `[45]` mbullon deget 2-3 — **e merre te plote** → 45
2. Nyja `[65]` mbullon deget 4-5 — **e merre te plote** → 65
3. **Pergjigja:** `45 + 65 = 110€`

Ne vend qe te vizitojme 4 elemente, vizituam vetem **2 nyje**!

### Pse eshte e shpejte?

Pema ka lartesi `log₂(n)`. Per 1 milion elemente, lartesia eshte vetem **~20**. Keshtu, cdo pyetje kerkon maksimumi ~20 hapa, jo 1 milion.

---

## Operacioni 2: Update (Ndryshimi)

### Shembull: "Dega 3 tash ka 50€ ne vend te 30€"

Ndryshon gjethen dhe update-on te gjitha nyjet prind:

```
Para:                           Pas:
        [45]                          [65]         ← 15+50=65
        / \                           / \
      15   30  ← ndryshon         15   50  ← u be 50
```

**Te gjitha nyjet siper update-ohen:**
```
Gjethja dega 3:  30 → 50   (+20)
Nyja [2-3]:      45 → 65   (+20)
Nyja [0-3]:      80 → 100  (+20)
Rrenja [0-7]:   230 → 250  (+20)
```

Vetem **4 nyje u ndryshuan** (lartesia e pemes), jo i gjithe array-i.

---

## Implementimi ne C++ — me komente

```cpp
#include <vector>
using namespace std;

class SegmentTree {
    vector<int> tree;  // pema ruhet si array
    int n;             // madhesia e array-it origjinal

    // Nderton pemen — therret veten rekursivisht
    void build(vector<int>& arr, int node, int start, int end) {
        if (start == end) {
            // Jemi ne gjeth — ruaj elementin
            tree[node] = arr[start];
        } else {
            int mid = (start + end) / 2;

            // Ndereto femijen e majte (gjysma e pare)
            build(arr, 2 * node, start, mid);

            // Ndereto femijen e djathte (gjysma e dyte)
            build(arr, 2 * node + 1, mid + 1, end);

            // Prindi = shuma e femijeve
            tree[node] = tree[2 * node] + tree[2 * node + 1];
        }
    }

    // Ndryshon nje element dhe update-on pemen
    void update(int node, int start, int end, int idx, int val) {
        if (start == end) {
            // Arritam te gjethja — vendos vleren e re
            tree[node] = val;
        } else {
            int mid = (start + end) / 2;

            if (idx <= mid) {
                // Elementi eshte ne gjysmen e majte
                update(2 * node, start, mid, idx, val);
            } else {
                // Elementi eshte ne gjysmen e djathte
                update(2 * node + 1, mid + 1, end, idx, val);
            }

            // Rillogarit prindin
            tree[node] = tree[2 * node] + tree[2 * node + 1];
        }
    }

    // Gjen shumen e elementeve nga pozita l deri ne r
    int query(int node, int start, int end, int l, int r) {
        // Rasti 1: segmenti eshte plotesisht JASHTE range-it
        if (r < start || end < l) {
            return 0; // nuk kontribuon asgje
        }

        // Rasti 2: segmenti eshte plotesisht BRENDA range-it
        if (l <= start && end <= r) {
            return tree[node]; // merre te gjithe
        }

        // Rasti 3: segmenti eshte PJESERISHT brenda — ndaje
        int mid = (start + end) / 2;
        int majta = query(2 * node, start, mid, l, r);
        int djathta = query(2 * node + 1, mid + 1, end, l, r);

        return majta + djathta;
    }

public:
    // Konstruktori — merr array-in dhe nderton pemen
    SegmentTree(vector<int>& arr) {
        n = arr.size();
        tree.resize(4 * n);   // 4*n eshte madhesia e sigurt
        build(arr, 1, 0, n - 1);
    }

    // Ndryshon elementin ne poziten idx me vleren val
    void update(int idx, int val) {
        update(1, 0, n - 1, idx, val);
    }

    // Kthen shumen e elementeve nga l deri ne r
    int query(int l, int r) {
        return query(1, 0, n - 1, l, r);
    }
};
```

### Perdorimi:

```cpp
int main() {
    //               dega0  dega1  dega2  dega3  dega4  dega5  dega6  dega7
    vector<int> shitjet = {10,   25,    15,    30,    20,    45,    35,    50};

    SegmentTree st(shitjet);

    // Pyetje: shuma e degeve 2-5
    cout << st.query(2, 5) << endl;    // Rezultati: 110

    // Update: dega 3 tash ka 50€
    st.update(3, 50);

    // Pyetje perseri: shuma e degeve 2-5
    cout << st.query(2, 5) << endl;    // Rezultati: 130 (15+50+20+45)

    return 0;
}
```

---

## Krahasimi i performances

| Operacioni | Array i thjeshte | Segment Tree |
|-----------|:---:|:---:|
| Ndertimi | O(n) | O(n) |
| Query (shuma e range) | **O(n)** — ngadalesht | **O(log n)** — shpejt |
| Update (nje element) | O(1) | O(log n) |
| Memoria | O(n) | O(4n) |

### Me numra konkret (per 1,000,000 elemente):

| | Array | Segment Tree |
|---|:---:|:---:|
| Query | ~1,000,000 hapa | ~20 hapa |
| Update | 1 hap | ~20 hapa |

> Segment Tree eshte perfekt kur ke **shume pyetje DHE shume update-e**. Nese ke vetem pyetje pa update, prefix sum eshte me i mire.

---

## Raste te perdorimit ne boten reale

### 1. Sistemi i monitorimit te serverave
Ke 10,000 servera. Cdo sekonde te duhet te dish:
- "Cili server ne range-in 500-800 ka ngarkesen me te larte?"
- Perdor Segment Tree me **operacionin MAX** ne vend te SUM.

### 2. Loja video — damage calculation
Nje lojtar sulmon armiqte ne pozitat 10-50 ne harte. Segment Tree llogarit damage-in total menjehere.

### 3. Analiza financiare
Ke cmimet ditore te aksioneve per 10 vjet (~2500 dite). Pyetje si "Cili ka qene cmimi minimal nga dita 100 deri 500?" pergjigjen me **operacionin MIN**.

### 4. Competitive Programming
Segment Tree eshte nje nga strukturat **me te rendesishme** ne gara programimi (Codeforces, USACO, IOI). Pothuajse cdo gare ka te pakten 1 problem qe zgjidhet me te.

---

## Variacionet e Segment Tree

| Varianti | Pershkrimi |
|----------|-----------|
| **Lazy Propagation** | Lejon update ne range (p.sh. "shto 5 te gjitha degeve 10-50") ne O(log n) |
| **Persistent** | Ruan te gjitha versionet e kaluara — mund te besh query ne cdo version |
| **2D Segment Tree** | Per matrica — query ne drejtkendesh |
| **Merge Sort Tree** | Cdo nyje mban nje liste te sortuar — per pyetje me te avancuara |

---

## Gabimet me te shpeshta

1. **Madhesia e array-it `tree`** — perdor `4 * n`, jo `2 * n`. Pema mund te kete nevoje per me shume hapesire.

2. **Indeksimi** — vendos nese fillon nga 0 apo 1 dhe qendro konsistent.

3. **Operacioni neutral** — per SUM kthe `0` kur je jashte range-it, per MIN kthe `INT_MAX`, per MAX kthe `INT_MIN`.

4. **Update harron prindin** — pas ndryshimit te gjethes, cdo nyje prind duhet rillogaritur.

---

## Permbledhje

Segment Tree eshte si nje **kalkulator i mencur** qe mban pergjigjje te gatshme per grupe te ndryshme te te dhenave. Kur ndryshon dicka, ai update-on vetem ato qe preken — jo te gjitha.

**Perdore kur:**
- Ke nje array te madhe
- Duhet te besh shume pyetje per range (shuma, min, max)
- Array-i ndryshon shpesh

**Mos e perdor kur:**
- Array-i nuk ndryshon kurre (perdor prefix sum)
- Ke vetem disa elemente (array i thjeshte mjafton)