forked from TheAlgorithms/Python
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathfenwick_tree.py
More file actions
29 lines (25 loc) · 787 Bytes
/
fenwick_tree.py
File metadata and controls
29 lines (25 loc) · 787 Bytes
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
from __future__ import print_function
class FenwickTree:
def __init__(self, SIZE): # create fenwick tree with size SIZE
self.Size = SIZE
self.ft = [0 for i in range (0,SIZE)]
def update(self, i, val): # update data (adding) in index i in O(lg N)
while (i < self.Size):
self.ft[i] += val
i += i & (-i)
def query(self, i): # query cumulative data from index 0 to i in O(lg N)
ret = 0
while (i > 0):
ret += self.ft[i]
i -= i & (-i)
return ret
if __name__ == '__main__':
f = FenwickTree(100)
f.update(1,20)
f.update(4,4)
print (f.query(1))
print (f.query(3))
print (f.query(4))
f.update(2,-5)
print (f.query(1))
print (f.query(3))