Fenwick Tree

what

• reference: Fenwick Tree - Algorithms for Competitive Programming
• exercices: Problem List - LeetCode

implementation

for range sum

class SumBIT:
 
    def __init__(self, nums: List[int]):
        n = len(nums)
        self.n = n
        self.nums = nums
        self.bit = [0] * n
        for i, x in enumerate(nums):
            self.bit[i] += x
            j = i | (i + 1)
            if j < n:
                self.bit[j] += self.bit[i]
 
    def update(self, i: int, val: int) -> None:
        d = val - self.nums[i]
        self.nums[i] = val
        while i < self.n:
            self.bit[i] += d
            i = i | (i + 1)
    
    def _sum(self, right):
        ans = 0
        while right >= 0:
            ans += self.bit[right]
            right = (right & (right + 1)) - 1
        
        return ans
 
    def sum_range(self, left: int, right: int) -> int:
        return self._sum(right) - self._sum(left - 1)