Project Template – Algorithm Design

Studenti: _____________________ Data: _____________________ Lënda: Algorithm Design

1. Qëllimi i Projektit

Problemi që do të zgjidhim

Në shumë sisteme softuerike, kemi nevojë të punojmë me sasi të mëdha të dhënash që ndryshojnë vazhdimisht, dhe njëkohësisht duhet të përgjigjemi shpejt në pyetje mbi grupe të caktuara të atyre të dhënave.

Për shembull, le ta marrim rastin e një kompanie me qindra degë marketesh në mbarë vendin. Çdo degë raporton shitjet e saj çdo ditë. Menaxhmenti ka nevojë të dijë përgjigje si:

"Sa janë shitjet totale nga dega 50 deri në degën 200?"
"Dega 75 ka raportuar shitje të reja — përditëso totalin!"

Nëse i ruajmë shitjet në një listë të thjeshtë dhe i mbledhim një nga një sa herë që na duhet përgjigjja, kjo bëhet tepër e ngadaltë kur kemi mijëra degë dhe mijëra pyetje në ditë. Nga ana tjetër, nëse e parallogarisim shumën totale paraprakisht, atëherë çdo ndryshim i vetëm na detyron ta rillogarisim gjithçka.

Ky tension midis pyetjeve të shpejta dhe ndryshimeve të shpejta është problemi thelbësor që do ta adresojmë.

Objektivat kryesore

Do të ndërtojmë një Segment Tree që i përgjigjet pyetjeve mbi range në O(log n) kohë
Do të mundësojmë përditësime të shpejta në O(log n) kohë
Do ta testojmë korrektësinë me shembuj konkretë
Do ta krahasojmë performancën me qasje alternative (brute force, prefix sum)

2. Përshkrimi i Problemit

Konteksti — Problemi i botës reale

Para se të flasim për zgjidhjen teknike, duhet ta kuptojmë mirë problemin që ekziston në praktikë.

Një zinxhir marketesh ka 1000 degë të shpërndara në mbarë vendin. Çdo degë raporton shitjet ditore në sistemin qendror. Menaxherët e rajoneve kanë nevojë të dinë vazhdimisht:

"Sa janë shitjet totale të degëve 100 deri 300?" — për ta ditur performancën e një rajoni
"Dega 250 ka mbyllur ditën — tani ka 12,500€ shitje" — përditësim i vlerës

Këto pyetje vijnë dhjetëra herë në ditë nga menaxherë të ndryshëm, për rajone të ndryshme. Njëkohësisht, degët vazhdojnë të raportojnë shitje të reja, pra vlerat ndryshojnë gjatë gjithë kohës.

Me një listë të thjeshtë, për t'i mbledhur vlerat e 200 degëve do të na duheshin 200 hapa. Me 1000 pyetje në ditë, kjo do të thoshte 200,000 operacione — shumë e ngadaltë kur sistemi duhet të përgjigjet në çast.

Na duhet një strukturë që na lejon t'i bëjmë të dy gjërat shpejt: pyetje mbi range dhe përditësime individuale.

Formulimi teknik i problemit

Duke e abstraguar rastin e mësipërm, problemi teknik që do të zgjidhim është:

Na jepet një array A me n numra të plotë, ku çdo element përfaqëson shitjen e një dege. Duhet të procesojmë q operacione, ku secili operacion është njëri nga dy llojet:

Query(l, r): Kthe shumën A[l] + A[l+1] + ... + A[r] — shitjet totale të degëve nga l deri r
Update(i, v): Vendos A[i] = v — dega i ka raportuar vlerën e re v

Input dhe Output

Input:

n = 8                                    (numri i degëve)
A = [10, 25, 15, 30, 20, 45, 35, 50]    (shitjet ditore në €)
q = 4                                    (numri i operacioneve)

Operacionet:
  Query(2, 5)       → Kthe shitjet totale nga dega 2 deri 5
  Update(3, 50)     → Dega 3 ka raportuar 50€
  Query(2, 5)       → Kthe shumën e re pas përditësimit
  Query(0, 7)       → Kthe shitjet totale të gjitha degëve

Output:

Query(2, 5) = 110    (15 + 30 + 20 + 45)
Update(3, 50)        (A bëhet [10, 25, 15, 50, 20, 45, 35, 50])
Query(2, 5) = 130    (15 + 50 + 20 + 45)
Query(0, 7) = 250    (10 + 25 + 15 + 50 + 20 + 45 + 35 + 50)

Kufizimet / Constraints

Parametri	Vlera
`n` (numri i degëve)	1 ≤ n ≤ 10⁶
`q` (numri i operacioneve)	1 ≤ q ≤ 10⁶
`A[i]` (shitjet në €)	-10⁹ ≤ A[i] ≤ 10⁹
`l, r` (range i query-t)	0 ≤ l ≤ r < n
Koha e lejuar	~2 sekonda

3. Zgjedhja e Algoritmit

Algoritmi i zgjedhur: Divide & Conquer → Segment Tree

Segment Tree-n e kemi zgjedhur sepse kombinon dy parime:

Divide & Conquer — e ndajmë array-in në gjysma rekursivisht
Strukturë peme — i ruajmë rezultatet e parallogaritura në nyje

Pse e kemi zgjedhur këtë algoritëm

Para se ta zgjidhnim Segment Tree-n, i kemi shqyrtuar edhe alternativat:

Qasja	Query	Update	A përshtatet?
Brute Force (loop)	O(n)	O(1)	Jo — query tepër i ngadaltë
Prefix Sum	O(1)	O(n)	Jo — update tepër i ngadaltë
Segment Tree	O(log n)	O(log n)	Po — i balancuar

Siç e shohim nga tabela, Segment Tree është i vetmi që e balancon kohën e query-t dhe update-it. Kur kemi shumë operacione nga të dy llojet, asnjë alternativë tjetër nuk e arrin këtë balancim.

Pseudo-code

FUNKSIONI BUILD(arr, node, start, end):
    NËSE start == end:
        tree[node] = arr[start]                         // gjethja = elementi
    PËRNDRYSHE:
        mid = (start + end) / 2
        BUILD(arr, 2*node, start, mid)                   // gjysma e majtë
        BUILD(arr, 2*node+1, mid+1, end)                 // gjysma e djathtë
        tree[node] = tree[2*node] + tree[2*node+1]       // prindi = shuma

FUNKSIONI QUERY(node, start, end, l, r):
    NËSE r < start OSE end < l:
        KTHE 0                                           // jashtë range-it
    NËSE l <= start DHE end <= r:
        KTHE tree[node]                                  // brenda plotësisht
    mid = (start + end) / 2
    KTHE QUERY(majta) + QUERY(djathta)                   // ndaje dhe mblidh

FUNKSIONI UPDATE(node, start, end, idx, val):
    NËSE start == end:
        tree[node] = val                                 // ndrysho gjethën
    PËRNDRYSHE:
        Zbrit në gjysmën ku ndodhet idx
        tree[node] = tree[majta] + tree[djathta]         // rillogarit prindin

Flowchart — Si funksionon Query(2, 5)

                    [0-7] 230
                  /            \
           [0-3] 80            [4-7] 150
          /      \             /       \
      [0-1]35   [2-3]45   [4-5]65   [6-7]85
      /  \      /   \      /  \      /  \
    10   25   15    30   20   45   35   50

Hapi 1: Rrënja [0-7] → range 2-5 është pjesërisht brenda → zbresim
Hapi 2: [0-3] → range 2-5 është pjesërisht brenda → zbresim
Hapi 3: [0-1] → range 2-5 është JASHTË → kthejmë 0
Hapi 4: [2-3] → range 2-5 është BRENDA PLOTËSISHT → e marrim 45 ✓
Hapi 5: [4-7] → range 2-5 është pjesërisht brenda → zbresim
Hapi 6: [4-5] → range 2-5 është BRENDA PLOTËSISHT → e marrim 65 ✓
Hapi 7: [6-7] → range 2-5 është JASHTË → kthejmë 0

Rezultati: 0 + 45 + 65 + 0 = 110 ✓

4. Implementimi

Gjuha e programimit: C# (.NET 8)

Strukturat e të dhënave të përdorura

Struktura	Përdorimi
`int[] _tree`	Ruan nyjet e pemës (madhësia 4×n)
`int _n`	Madhësia e array-it origjinal

Pse `4 × n`?

Pema binare me n gjethë ka maksimumi 2n - 1 nyje. Megjithatë, meqë e kemi ruajtur pemën si array me indeksim 2*node dhe 2*node+1, na duhen deri në 4n pozita për ta mbuluar rastin më të keq. Kështu, kemi zgjedhur 4 * n si madhësi të sigurt.

Kodi i plotë

namespace SegmentTreeDemo;

/// <summary>
/// Segment Tree — strukturë e të dhënave që mundëson range query
/// dhe point update në O(log n) kohë.
/// </summary>
public class SegmentTree
{
    private readonly int[] _tree;
    private readonly int _n;

    /// <summary>
    /// Ndërton Segment Tree nga array-i i dhënë.
    /// Kompleksiteti: O(n)
    /// </summary>
    public SegmentTree(int[] arr)
    {
        _n = arr.Length;
        _tree = new int[4 * _n];
        Build(arr, node: 1, start: 0, end: _n - 1);
    }

    /// <summary>
    /// Kthen shumën e elementeve nga pozita l deri në r (përfshirëse).
    /// Kompleksiteti: O(log n)
    /// </summary>
    public int Query(int l, int r)
    {
        return Query(node: 1, start: 0, end: _n - 1, l, r);
    }

    /// <summary>
    /// Ndryshon elementin në pozitën idx me vlerën e re val.
    /// Kompleksiteti: O(log n)
    /// </summary>
    public void Update(int idx, int val)
    {
        Update(node: 1, start: 0, end: _n - 1, idx, val);
    }

    // ================================================================
    // METODAT PRIVATE
    // ================================================================

    /// <summary>
    /// Ndërton pemën rekursivisht.
    /// Çdo gjethë mban një element të array-it.
    /// Çdo nyje prind mban shumën e dy fëmijëve.
    /// </summary>
    private void Build(int[] arr, int node, int start, int end)
    {
        if (start == end)
        {
            // Rasti bazë: kemi arritur te gjethja.
            // E ruajmë elementin e array-it direkt në nyje.
            _tree[node] = arr[start];
            return;
        }

        int mid = (start + end) / 2;

        // Ndërtojmë nënpemën e majtë (gjysma e parë e segmentit)
        Build(arr, node: 2 * node, start, end: mid);

        // Ndërtojmë nënpemën e djathtë (gjysma e dytë e segmentit)
        Build(arr, node: 2 * node + 1, start: mid + 1, end);

        // Nyja prind = shuma e dy fëmijëve
        _tree[node] = _tree[2 * node] + _tree[2 * node + 1];
    }

    /// <summary>
    /// Gjen shumën e elementeve në range-in [l, r].
    /// Punon duke zbritur pemën dhe duke kombinuar vetëm
    /// segmentet që preken nga range-i i kërkuar.
    /// </summary>
    private int Query(int node, int start, int end, int l, int r)
    {
        // RASTI 1: Segmenti [start, end] nuk prek fare range-in [l, r].
        // Shembull: po kërkojmë [2, 5] por jemi në nyjen [6, 7].
        // Ky segment nuk kontribuon asgjë, pra kthejmë 0.
        if (r < start || end < l)
        {
            return 0;
        }

        // RASTI 2: Segmenti [start, end] bie plotësisht brenda [l, r].
        // Shembull: po kërkojmë [2, 5] dhe jemi në nyjen [2, 3].
        // E marrim vlerën e kësaj nyje direkt, pa pasur nevojë të zbresim më thellë.
        if (l <= start && end <= r)
        {
            return _tree[node];
        }

        // RASTI 3: Segmenti mbulohet pjesërisht — e ndajmë në dy gjysma
        // dhe i mbledhim rezultatet.
        int mid = (start + end) / 2;
        int leftSum = Query(node: 2 * node, start, end: mid, l, r);
        int rightSum = Query(node: 2 * node + 1, start: mid + 1, end, l, r);

        return leftSum + rightSum;
    }

    /// <summary>
    /// Ndryshon vlerën e elementit në pozitën idx.
    /// Zbret deri te gjethja, e ndryshon, dhe pastaj rillogarit
    /// çdo nyje prind në rrugën kthyese deri në rrënjë.
    /// </summary>
    private void Update(int node, int start, int end, int idx, int val)
    {
        if (start == end)
        {
            // Kemi arritur te gjethja që duam ta ndryshojmë.
            // E vendosim vlerën e re.
            _tree[node] = val;
            return;
        }

        int mid = (start + end) / 2;

        if (idx <= mid)
        {
            // Elementi ndodhet në gjysmën e majtë — zbresim majtas
            Update(node: 2 * node, start, end: mid, idx, val);
        }
        else
        {
            // Elementi ndodhet në gjysmën e djathtë — zbresim djathtas
            Update(node: 2 * node + 1, start: mid + 1, end, idx, val);
        }

        // Pasi e kemi ndryshuar gjethën, rillogarisim nyjen prind
        // duke mbledhur dy fëmijët e saj.
        _tree[node] = _tree[2 * node] + _tree[2 * node + 1];
    }
}

Programi kryesor — Demonstrimi

namespace SegmentTreeDemo;

public class Program
{
    public static void Main()
    {
        //            dega0  dega1  dega2  dega3  dega4  dega5  dega6  dega7
        int[] shitjet = [10,   25,    15,    30,    20,    45,    35,    50];

        var st = new SegmentTree(shitjet);

        // Query 1: Kërkojmë shumën e degëve 2-5
        Console.WriteLine($"Query(2,5) = {st.Query(2, 5)}");   // 110

        // Update: Dega 3 tani ka 50€ në vend të 30€
        st.Update(3, 50);
        Console.WriteLine("Update(3, 50) — dega 3 u përditësua");

        // Query 2: E bëjmë të njëjtën pyetje pas ndryshimit
        Console.WriteLine($"Query(2,5) = {st.Query(2, 5)}");   // 130

        // Query 3: Kërkojmë shumën totale të gjitha degëve
        Console.WriteLine($"Query(0,7) = {st.Query(0, 7)}");   // 250
    }
}

Output i pritshëm:

Query(2,5) = 110
Update(3, 50) — dega 3 u përditësua
Query(2,5) = 130
Query(0,7) = 250

Hapat kryesorë të implementimit

Alokimi i memories — Krijojmë int[] _tree me madhësi 4 * n
Ndërtimi (Build) — E mbushim pemën rekursivisht nga array-i, O(n)
Query — Zbresim pemën, marrim vetëm segmentet relevante, O(log n)
Update — Ndryshojmë gjethën, rillogarisim prindërit deri në rrënjë, O(log n)

5. Testimi

Për ta verifikuar korrektësinë e implementimit, kemi përgatitur gjashtë test case që mbulojnë raste normale, ndryshime, dhe edge case.

Test Case 1 — Query bazik

Input:  A = [10, 25, 15, 30, 20, 45, 35, 50]
        Query(2, 5)
Pritur: 110 (15 + 30 + 20 + 45)
Marrë:  110 ✓

Test Case 2 — Update pastaj Query

Input:  Update(3, 50)    → A bëhet [10, 25, 15, 50, 20, 45, 35, 50]
        Query(2, 5)
Pritur: 130 (15 + 50 + 20 + 45)
Marrë:  130 ✓

Test Case 3 — Query i plotë (i gjithë array-i)

Input:  Query(0, 7)
Pritur: 250 (10 + 25 + 15 + 50 + 20 + 45 + 35 + 50)
Marrë:  250 ✓

Test Case 4 — Query për një element të vetëm

Input:  Query(4, 4)
Pritur: 20
Marrë:  20 ✓

Test Case 5 — Edge Case: Array me 1 element

Input:  A = [42]
        Query(0, 0)
Pritur: 42
Marrë:  42 ✓

Test Case 6 — Numra negativë

Input:  A = [-5, 10, -3, 8]
        Query(0, 3)
Pritur: 10 (-5 + 10 + -3 + 8)
Marrë:  10 ✓

Analiza e saktësisë

Të gjashtë test case-et kanë kaluar me sukses. Rezultatet e marra përputhen plotësisht me rezultatet e pritura. Testimi ynë ka mbuluar:

Raste normale — query në range mesatar
Update + Query — verifikim pas ndryshimit
Edge cases — array me 1 element, element i vetëm, numra negativë
Query i plotë — mbi gjithë array-in

6. Analiza e Kompleksitetit

Time Complexity

Operacioni	Kompleksiteti	Arsyeja
Build	O(n)	Vizitojmë çdo nyje saktësisht një herë. Pema ka ~2n nyje
Query	O(log n)	Në çdo nivel të pemës, vizitojmë maksimumi 4 nyje. Pema ka log₂(n) nivele
Update	O(log n)	Ndjekim vetëm një shteg nga rrënja deri te gjethja — sa lartësia e pemës

Për q operacione totale: O(n + q × log n)

Space Complexity

Komponenti	Hapësira
Array-i `_tree`	O(4n) = O(n)
Stack i rekursionit	O(log n) — thellësia e pemës
Totale	O(n)

Faktorët që ndikojnë në performancë

1. Madhësia e array-it (n) Kur n rritet, ndërtimi merr më shumë kohë, por query dhe update mbeten O(log n). Për shembull, me n = 1,000,000 degë, log₂(n) ≈ 20, që do të thotë se çdo query do të bëjë vetëm ~20 krahasime.

2. Numri i operacioneve (q) Segment Tree shkëlqen kur q është i madh — domethënë kur kemi shumë pyetje dhe shumë ndryshime njëkohësisht. Nëse do të kishim vetëm 1-2 pyetje pa ndryshime, brute force do të mjaftonte.

3. Cache performance Meqë pemën e kemi ruajtur si array (jo me pointera), kemi përfitim nga cache locality — nyjet fqinje në pemë ndodhen afër edhe në memorie, gjë që e shpejton aksesimin.

4. Tipi i operacionit Segment Tree funksionon me çdo operacion që është asocativ: SUM, MIN, MAX, GCD, XOR, etj. Kushti është që a ⊕ (b ⊕ c) = (a ⊕ b) ⊕ c.

7. Krahasimi me Algoritme të Tjerë

Alternativa 1: Brute Force (Loop i thjeshtë)

Për Query(l, r): shkojmë nga l deri r, mbledhim vlerat
Për Update(i, v): A[i] = v

	Brute Force	Segment Tree
Query	O(n)	O(log n)
Update	O(1)	O(log n)
Build	O(1)	O(n)
Hapësira	O(n)	O(4n)

Kur do ta zgjidhnim Brute Force? Kur kemi shumë update por pak query, ose kur n është shumë i vogël (nën 100 elemente).

Alternativa 2: Prefix Sum

Ndërtojmë: prefix[i] = A[0] + A[1] + ... + A[i]
Query(l, r) = prefix[r] - prefix[l-1]
Update(i, v) = rillogarisim prefix nga i deri n

	Prefix Sum	Segment Tree
Query	O(1)	O(log n)
Update	O(n)	O(log n)
Build	O(n)	O(n)

Kur do ta zgjidhnim Prefix Sum? Kur nuk kemi update fare — vetëm pyetje. Në atë rast, query O(1) është e pakapërcyeshme.

Alternativa 3: Binary Indexed Tree (BIT / Fenwick Tree)

	BIT	Segment Tree
Query	O(log n)	O(log n)
Update	O(log n)	O(log n)
Hapësira	O(n)	O(4n)
Implementimi	Më i thjeshtë	Më i ndërlikuar
Fleksibiliteti	Vetëm SUM	SUM, MIN, MAX, etj.

Kur do ta zgjidhnim BIT? Kur na duhet vetëm operacioni SUM dhe dëshirojmë kod më të shkurtër me më pak memorie.

Tabela përmbledhëse — Kur ta përdorim secilin

Vetëm Query pa Update?  →  Prefix Sum
Vetëm SUM?              →  BIT (më i thjeshtë)
SUM + MIN + MAX?        →  Segment Tree ✓
n < 100?                →  Brute Force

Segment Tree-n e kemi zgjedhur sepse na ofron fleksibilitet maksimal — mbështet çdo operacion asocativ dhe ka performancë të balancuar si për query ashtu edhe për update.

8. Përfundimet

Çfarë kemi mësuar nga ky projekt

Divide & Conquer nuk përdoret vetëm për sorting — me të kemi ndërtuar një strukturë të fuqishme të dhënash
Kemi kuptuar trade-off-in midis kohës dhe hapësirës — Segment Tree përdor 4× më shumë memorie, por na fiton shpejtësi eksponenciale në query
Rekursioni ka qenë çelësi — ndërtimi, query, dhe update janë të gjitha rekursive me strukturë të ngjashme, gjë që e bën kodin elegant
Kemi mësuar si të zgjedhim algoritmin e duhur duke krahasuar kompleksitetin e alternativave me kërkesat e problemit

Përmirësime të mundshme

Përmirësimi	Përshkrimi
Lazy Propagation	Do të na lejonte range update (p.sh. "shto 5 te gjitha degët 10-50") në O(log n)
Iterative Build	Do ta eliminonte rekursionin duke ndërtuar bottom-up — pak më i shpejtë
Persistent Segment Tree	Do të na ruante versionet e kaluara — e dobishme për time-travel queries
Generic<T>	Do ta bënim klasën generike në C# për të mbështetur tipe të ndryshme (long, double)

Përdorimi real i këtij algoritmi

Databaza — Range queries mbi indekse (p.sh. "gjej rekordet me datë midis X dhe Y")
Zinxhirë marketesh — Llogaritja e shitjeve totale për rajone të ndryshme në kohë reale
Lojëra video — Llogaritja e damage-it total në zona të hartës
Financa — Analiza e çmimeve të aksioneve: min/max/average në periudha kohore
Competitive Programming — Ndër strukturat më të përdorura në IOI, ICPC, dhe Codeforces

9. Referencat

Burimi	Përshkrimi
Introduction to Algorithms (CLRS)	Kapitulli mbi Divide & Conquer dhe Data Structures
Competitive Programmer's Handbook	Antti Laaksonen — Kapitulli 9: Range Queries
CP-Algorithms	cp-algorithms.com — Segment Tree
GeeksforGeeks	geeksforgeeks.org — Segment Tree: Sum of given range
Microsoft Learn	Dokumentacioni zyrtar i C# dhe .NET 8
Visualgo	visualgo.net — Vizualizim interaktiv i Segment Tree