Conas a thacaíonn crann-bharaig agus crann Fenwick (BIT) fiosrúcháin raoin tapa?

Question

IT Interview Practice · Accepted Answer

Tugann **crann-bharaig** agus **crann Fenwick** (Binary Indexed Tree, BIT) araon freagra ar **fiosrúcháin raoin** (e.g. suim thar `[l, r]`) agus **nuashonruithe pointe** in **O(log n)**, i gcomparáid le O(n) do scan simplí nó O(n) nuashonruithe do bhreiseán réamhfhocail-shuim.

## An fhadhb a réitíonn siad

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

## Crann Fenwick (BIT) — dlúth agus elegánt

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

## Crann-bharaig — níos ginearálta

Stóraíonn crann-bharaig drochur ar fach mhíreanna an tsraith i gcrann dhénártha, ag tacú le **aon oibríocht chomhchaidreamhach** (suim, min, max, gcd) agus, le propagation mall, **nuashonruithe raoin** freisin.

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

## Comparáid

| | Fenwick (BIT) | Crann-bharaig |
|---|---|---|
| Fiosrúchán / nuashonrú | O(log n) | O(log n) |
| Spás | O(n) | O(2n) |
| Oibríochtaí | suimeanna (inbhéartaithe) | aon oibríocht chomhchaidreamhach |
| Nuashonruithe raoin | níos deacra | éasca (lazy propagation) |
| Méid an chóid | beag go mór | níos mó |

## Cén fáth ar chóir a bheith i gceist

Tuigeann na struchtúir seo "luach a nuashonrú, ansin drochur a fhiosrúchán thar raon" a dhéanamh go tapa — riachtanach do chláradh iomaíochach, fuinneoga anailíse, agus fadhbanna eatramh.

Tá rogha idir iad ar dhealú: tá crann Fenwick beag agus tapa do shuimeanna, agus tá crann-bharaig níos solúbtha do mhuingceanna min/max/nuashonrú-raoin.

	Fenwick (BIT)	Crann-bharaig
Fiosrúchán / nuashonrú	O(log n)	O(log n)
Spás	O(n)	O(2n)
Oibríochtaí	suimeanna (inbhéartaithe)	aon oibríocht chomhchaidreamhach
Nuashonruithe raoin	níos deacra	éasca (lazy propagation)
Méid an chóid	beag go mór	níos mó

An fhadhb a réitíonn siad

Crann Fenwick (BIT) — dlúth agus elegánt

Crann-bharaig — níos ginearálta

Comparáid

Cén fáth ar chóir a bheith i gceist

Ceisteanna gaolmhara