prefix sum کیا ہے، اور یہ range queries کو تیز کرنے میں کس طرح مدد دیتا ہے؟

Question

IT Interview Practice · Accepted Answer

ایک **prefix sum** array cumulative totals کو store کرتا ہے تاکہ کوئی بھی **range sum** O(n) preprocessing کے بعد **O(1)** میں جواب دیا جا سکے — بجائے ہر query کے لیے O(n) کے۔

## The idea

آئیے `prefix[i]` پہلے `i` عناصر کا مجموعہ ہو۔ پھر `arr[l..r]` کا مجموعہ `prefix[r+1] - prefix[l]` ہے۔

## Example

```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
```

## Trace

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

## Complexity

- **Build:** O(n)۔ **Query:** O(1)۔ **Space:** O(n)۔

## کب استعمال کریں / خطرات

Static data پر **بہت سے range-sum queries** کے لیے موزوں۔ Variants: 2D prefix sums submatrix sums کے لیے، prefix XOR، اور difference arrays range updates کے لیے۔ اگر array اکثر بدلتا ہے، تو اس کی بجائے Fenwick/segment tree استعمال کریں۔ Index offset کا خیال رکھیں (سائز n+1)۔

## اس کی اہمیت کیوں ہے

Prefix sums بار بار O(n) range queries کو O(1) lookups میں بدل دیتے ہیں — جب queries اکثر ہوں تو یہ بہت بڑی جیت ہے۔

Precompute-once، answer-fast pattern بہت سے data-processing tasks میں عام ہے۔

یہ competitive programming کا ایک لازمی حصہ ہے اور analytics میں ایک عام بنیادی بلاک ہے۔

The idea

Example

Trace

Complexity

کب استعمال کریں / خطرات

اس کی اہمیت کیوں ہے

متعلقہ سوالات