FilesExpand file tree

 master

/

fenwick_tree.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

28 lines (24 loc) · 734 Bytes

 master

/

fenwick_tree.py

Copy path

Top

File metadata and controls

• Code
• Blame

28 lines (24 loc) · 734 Bytes

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

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))