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)