ਸੈਗਮੈਂਟ ਰੁੱਖ ਅਤੇ Fenwick ਰੁੱਖ (BIT) ਤੇਜ਼ ਰੇਂਜ ਖੋਜਾਂ ਨੂੰ ਕਿਵੇਂ ਸਮਰਥਨ ਕਰਦੇ ਹਨ?

Question

Accepted Answer

ਇੱਕ **ਸੈਗਮੈਂਟ ਰੁੱਖ** ਅਤੇ ਇੱਕ **Fenwick ਰੁੱਖ** (Binary Indexed Tree, BIT) ਦੋਨੋਂ **ਰੇਂਜ ਖੋਜਾਂ** (ਜਿਵੇਂ `[l, r]` ਉੱਤੇ ਜੋੜ) ਅਤੇ **ਬਿੰਦੂ ਅਪਡੇਟਸ** ਨੂੰ **O(log n)** ਵਿੱਚ ਜਵਾਬ ਦਿੰਦੇ ਹਨ, ਇੱਕ ਭੋਲੇ ਸਕੈਨ ਲਈ O(n) ਜਾਂ ਇੱਕ ਪ੍ਰਿਫਿਕਸ-ਸਮ ਐਰੇ ਲਈ O(n) ਅਪਡੇਟਸ ਦੇ ਮੁਕਾਬਲੇ।

## ਸਮੱਸਿਆ ਜੋ ਉਹ ਹੱਲ ਕਰਦੇ ਹਨ

```text
Array + many "sum of range [l,r]" and "update index i" calls:
  naive prefix sums: query O(1) but UPDATE is O(n)
  segment/Fenwick:   query O(log n) AND update O(log n)
```

## Fenwick ਰੁੱਖ (BIT) — ਸੰਖੇਪ ਅਤੇ ਖੂਬਸੂਰਤ

```python
class Fenwick:
    def __init__(self, n):
        self.t = [0]*(n+1)
    def update(self, i, delta):        # O(log n)
        i += 1
        while i < len(self.t):
            self.t[i] += delta
            i += i & (-i)              # jump to next responsible node
    def prefix(self, i):               # sum of [0..i], O(log n)
        i += 1; s = 0
        while i > 0:
            s += self.t[i]
            i -= i & (-i)
        return s
    def range_sum(self, l, r):
        return self.prefix(r) - self.prefix(l-1)
```

## ਸੈਗਮੈਂਟ ਰੁੱਖ — ਵਧੇਰੇ ਆਮ

ਇੱਕ ਸੈਗਮੈਂਟ ਰੁੱਖ ਇੱਕ ਬਾਈਨਰੀ ਰੁੱਖ ਵਿੱਚ ਪ੍ਰਤੀ ਐਰੇ ਸੈਗਮੈਂਟ ਇੱਕ ਅਨੁਮਾਨ ਸਟੋਰ ਕਰਦਾ ਹੈ, **ਕਿਸੇ ਵੀ ਐਸੋਸਿਏਟਿਵ ਓਪਰੇਸ਼ਨ** ਦਾ ਸਮਰਥਨ ਕਰਦੇ ਹੋਏ (ਜੋੜ, ਘੱਟ, ਵੱਧ, gcd) ਅਤੇ, lazy propagation ਦੇ ਨਾਲ, **ਰੇਂਜ ਅਪਡੇਟਸ** ਵੀ।

```text
        [0..7] sum
       /          \
   [0..3]         [4..7]
   /    \         /    \
 [0..1][2..3]  [4..5][6..7]   ... down to single elements
```

## ਤੁਲਨਾ

| | Fenwick (BIT) | ਸੈਗਮੈਂਟ ਰੁੱਖ |
|---|---|---|
| ਖੋਜ / ਅਪਡੇਟ | O(log n) | O(log n) |
| ਸਪੇਸ | O(n) | O(2n) |
| ਓਪਰੇਸ਼ਨਸ | ਜੋੜ (ਇਨਵਰਟੀਬਲ) | ਕਿਸੇ ਵੀ ਐਸੋਸਿਏਟਿਵ ਓਪ |
| ਰੇਂਜ ਅਪਡੇਟਸ | ਕਠਿਨ | ਆਸਾਨ (lazy propagation) |
| ਕੋਡ ਆਕਾਰ | ਬਹੁਤ ਛੋਟਾ | ਵੱਡਾ |

## ਇਹ ਕਿਉਂ ਮਹੱਤਵਪੂਰਨ ਹੈ

ਇਹ ਸਟ੍ਰਕਚਰ "ਇੱਕ ਮਾਨ ਨੂੰ ਅਪਡੇਟ ਕਰਿਆ, ਫਿਰ ਇੱਕ ਰੇਂਜ ਉੱਤੇ ਇੱਕ ਅਨੁਮਾਨ ਲਈ ਖੋਜ ਕੀਤੀ" ਤੇਜ਼ ਬਣਾਉਂਦੇ ਹਨ — ਮੁਕਾਬਲੇ ਪ੍ਰੋਗ੍ਰਾਮਿੰਗ, ਵਿਸ਼ਲੇਸ਼ਣ ਵਿੰਡੋ ਅਤੇ ਅੰਤਰਾਲ ਸਮੱਸਿਆਵਾਂ ਲਈ ਜ਼ਰੂਰੀ।

ਉਨ੍ਹਾਂ ਵਿਚਕਾਰ ਚੁਣਨਾ ਇੱਕ ਟਰੇਡ-ਆਫ ਹੈ: ਇੱਕ Fenwick ਰੁੱਖ ਜੋੜਾਂ ਲਈ ਛੋਟਾ ਅਤੇ ਤੇਜ਼ ਹੈ, ਜਦਕਿ ਇੱਕ ਸੈਗਮੈਂਟ ਰੁੱਖ min/max/ਰੇਂਜ-ਅਪਡੇਟ ਕਾਰਜ ਲੋਡਾਂ ਲਈ ਵਧੇਰੇ ਲਚਕਦਾਰ ਹੈ।

	Fenwick (BIT)	ਸੈਗਮੈਂਟ ਰੁੱਖ
ਖੋਜ / ਅਪਡੇਟ	O(log n)	O(log n)
ਸਪੇਸ	O(n)	O(2n)
ਓਪਰੇਸ਼ਨਸ	ਜੋੜ (ਇਨਵਰਟੀਬਲ)	ਕਿਸੇ ਵੀ ਐਸੋਸਿਏਟਿਵ ਓਪ
ਰੇਂਜ ਅਪਡੇਟਸ	ਕਠਿਨ	ਆਸਾਨ (lazy propagation)
ਕੋਡ ਆਕਾਰ	ਬਹੁਤ ਛੋਟਾ	ਵੱਡਾ