Segment tree da Fenwick tree (Binary Indexed Tree, BIT) duka suna amsa range queries (misali jiya akan [l, r]) da point updates a cikin O(log n), kwatankwa da O(n) don kanshu bataura ko O(n) updates don jiya hoto array.
Segment tree da Fenwick tree (Binary Indexed Tree, BIT) duka suna amsa range queries (misali jiya akan [l, r]) da point updates a cikin O(log n), kwatankwa da O(n) don kanshu bataura ko O(n) updates don jiya hoto array.
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)
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)
Segment tree yana ajiye aggregate bayan wannan sashen jiya a cikin binary tree, yana goyan aiki kowane aiki na shawara (jiya, min, max, gcd) da, tare da lazy propagation, range updates ma.
[0..7] sum
/ \
[0..3] [4..7]
/ \ / \
[0..1][2..3] [4..5][6..7] ... down to single elements
| Fenwick (BIT) | Segment tree | |
|---|---|---|
| Query / update | O(log n) | O(log n) |
| Space | O(n) | O(2n) |
| Operations | jiya (inverse) | kowane aiki na shawara |
| Range updates | wahala | sauƙi (lazy propagation) |
| Code size | karami | mafi girma |
Wannan gidaje suna sa "update value, sannan query aggregate akan kadan" a hanzari — muhimmi ne don sha'awar gida, windows na analysis, da matsaloli na taka.
Samun tsakiya a tsakiya shine sake-daidai: Fenwick tree yana karami da mabilis don jiya, yayin da segment tree ya kasance mafi flexible don min/max/range-update aiki.