Fenwick Tree / Binary Indexed Tree

datastructure

Fenwick Tree, or Binary Indexed Tree, is a data structure for range queries.
It is similar to Segment Tree, however

A simple implementation for constructing Fenwick Tree and query ranges is as following. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class NumArray:

    def __init__(self, nums):
        """
        :type nums: List[int]
        """
        self.nums = nums
        self.nums.insert(0, 0) # one-based
        self.l = len(nums)
        self.tree = [0 for i in range(self.l)]
        # construct tree
        for i in range(1, self.l + 1):
            start = i
            while start < len(self.tree):
                self.tree[start] += self.nums[i]
                start += self.lowbit(start)


    def lowbit(self, x):
        return x & -x

    def update(self, i, val):
        """
        :type i: int
        :type val: int
        :rtype: void
        """
        start = i + 1
        diff = val - self.nums[start]
        while start < len(self.tree):
            self.tree[start] += diff
            start += self.lowbit(start)
        self.nums[i + 1] = val
        

    def sumRange(self, i, j):
        """
        :type i: int
        :type j: int
        :rtype: int
        """
        # inclusive [, ]
        def sum_start(n):
            ans = 0
            while n != 0:
                ans += self.tree[n]
                n -= self.lowbit(n)
            return ans
        # make it one based
        return sum_start(j + 1) - sum_start(i)