md-platform

segment-tree.md
View raw Back to list

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:

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:

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

#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:

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:

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:

Mos e perdor kur: