რა არის პრეფიქსის ჯამი და როგორ აჩქარებს ის დიაპაზონის შეკითხვებს?

Question

Accepted Answer

**პრეფიქსის ჯამი** მასივი ინახავს კუმულაციურ ჯამებს, ასე რომ ნებისმიერი **დიაპაზონის ჯამი** შეიძლება გამოცემული იყოს **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).

## როდის გამოიყენება / არტიფაქტები

იდეალური **მრავალი დიაპაზონის ჯამის შეკითხვებისთვის** სტატიკურ მონაცემებზე. ვარიაციები: 2D პრეფიქსის ჯამი ქვემატრიცის ჯამებისთვის, პრეფიქსი XOR და განსხვავება მასივები დიაპაზონის განახლებებისთვის. თუ მასივი ხშირად იცვლება, ব্যবহარեთ Fenwick/segment tree. ნიშვნით გაფრთხოვება (ზომა n+1).

## რატომ არის მნიშვნელოვანი

პრეფიქსის ჯამი ყოვლ დროისა O(n) დიაპაზონის შეკითხვებს აკეთებს O(1) ძებნებით — უশუალო გაზე როდესაც შეკითხვები ხშირია.

წინამუშაობა-ერთხელ, პასუხი-სწრაფი ნიმუში განზოგადდა მრავალ მონაცემთა დამუშავების ამოცანებზე.

ესაა კონკურენციული პროგრამირების ფუნდამენტური და ანალიტიკაში საერთო სამშენებლო ბლოკი.