Fenwick Trees or Binary Indexed Tree
- Each index in the fenwick tree is responsible for a rnage of values in the original array.
- Requires $O(n)$ storage.
- Can calculate prefix sums in $O(\log n)$ time.
- Point updates can also be performed in $O(\log n)$
- Can only do operations which are invertible.
References
- https://cp-algorithms.com/data_structures/fenwick.html
- https://www.youtube.com/watch?v=uSFzHCZ4E-8
- https://blog.kartynnik.info/posts/fenwick-trees-are-nothing-but
0ยท 1ยท 2ยท 3ยท 4ยท 5ยท 6ยท 7ยท 8ยท 9ยท10ยท11ยท12ยท13ยท14ยท15
A = [ | | | | | | | | | | | | | | | ]
T[ 0] = [ โ| | | | | | | | | | | | | | | ]
T[ 1] = [ โ| โ| | | | | | | | | | | | | | ]
T[ 2] = [ | | โ| | | | | | | | | | | | | ]
T[ 3] = [ โ| โ| โ| โ| | | | | | | | | | | | ]
T[ 4] = [ | | | | โ| | | | | | | | | | | ]
T[ 5] = [ | | | | โ| โ| | | | | | | | | | ]
T[ 6] = [ | | | | | | โ| | | | | | | | | ]
T[ 7] = [ โ| โ| โ| โ| โ| โ| โ| โ| | | | | | | | ]
T[ 8] = [ | | | | | | | | โ| | | | | | | ]
T[ 9] = [ | | | | | | | | โ| โ| | | | | | ]
T[10] = [ | | | | | | | | | | โ| | | | | ]
T[11] = [ | | | | | | | | โ| โ| โ| โ| | | | ]
T[12] = [ | | | | | | | | | | | | โ| | | ]
T[13] = [ | | | | | | | | | | | | โ| โ| | ]
T[14] = [ | | | | | | | | | | | | | | โ| ]
T[15] = [ โ| โ| โ| โ| โ| โ| โ| โ| โ| โ| โ| โ| โ| โ| โ| โ]
OP = lambda a, b: a+b
OP_INV = lambda a, b: a - b
E = lambda : 0
class FenwickTree:
def __init__(self, A: List[int]):
n = len(A)
self.T = A.copy()
for i in range(n):
parent = i | (i + 1)
if parent < n:
self.T[parent] += self.T[i]
def add(self, i, delta):
n = len(self.T)
while i < n:
self.T[i] = OP(self.T[i], delta)
i = i | (i + 1)
def prefix_sum(self, i): # sum [0, i]
res = E()
while i >= 0:
res = OP(result, self.T[i])
i = (i & (i + 1)) - 1
return result
def range_sum(self, l, r): # sum [l, r)
return OP_INV(self.prefix_sum(r - 1) , self.prefix_sum(l - 1))
def __getitem__(self, idx: int) -> int:
return self.sum_range(idx, idx)
def append(self, val):
n = len(self.T)
self.T.append(E())
self.add(n, val)