Τι είναι ένα prefix sum και πώς επιταχύνει τα range queries;

Question

IT Interview Practice · Accepted Answer

Ένας πίνακας **prefix sum** αποθηκεύει αθροιστικά σύνολα ώστε οποιοδήποτε **range sum** να μπορεί να απαντηθεί σε **O(1)** μετά από O(n) προεπεξεργασία — αντί O(n) ανά ερώτημα.

## Η ιδέα

Έστω `prefix[i]` το άθροισμα των πρώτων `i` στοιχείων. Τότε το άθροισμα του `arr[l..r]` είναι `prefix[r+1] - prefix[l]`.

## Παράδειγμα

```python
def build_prefix(arr):
    prefix = [0] * (len(arr) + 1)
    for i, x in enumerate(arr):
        prefix[i + 1] = prefix[i] + x   # running total
    return prefix

def range_sum(prefix, l, r):            # inclusive l..r
    return prefix[r + 1] - prefix[l]    # O(1)

p = build_prefix([2, 4, 1, 3, 5])
range_sum(p, 1, 3)                      # 4+1+3 -> 8
```

## Ανίχνευση

```text
arr    = [2, 4, 1, 3, 5]
prefix = [0, 2, 6, 7, 10, 15]
sum(1..3) = prefix[4] - prefix[1] = 10 - 2 = 8
```

## Πολυπλοκότητα

- **Κατασκευή:** O(n). **Ερώτημα:** O(1). **Χώρος:** O(n).

## Πότε να χρησιμοποιήσετε / Παγίδες

Ιδανικό για **πολλά range-sum ερωτήματα** σε στατικά δεδομένα. Παραλλαγές: 2D prefix sums για αθροίσματα υποπινάκων, prefix XOR και difference arrays για ενημερώσεις εύρους. Αν το array αλλάζει συχνά, χρησιμοποιήστε αντί αυτού ένα Fenwick/segment tree. Προσέξτε την μετατόπιση δείκτη (μέγεθος n+1).

## Γιατί είναι σημαντικό

Τα prefix sums μετατρέπουν επαναλαμβανόμενα O(n) range queries σε O(1) lookups — ένα τεράστιο κέρδος όταν τα ερωτήματα είναι συχνά.

Το μοτίβο της προ-υπολογισμού και της γρήγορης απάντησης γενικεύεται σε πολλές εργασίες επεξεργασίας δεδομένων.

Είναι θεμέλιο της ανταγωνιστικής προγραμματισμού και ένα συνηθισμένο δομικό στοιχείο στην ανάλυση.

Η ιδέα

Παράδειγμα

Ανίχνευση

Πολυπλοκότητα

Πότε να χρησιμοποιήσετε / Παγίδες

Γιατί είναι σημαντικό

Σχετικές ερωτήσεις