| 1 | from __future__ import print_function |
| 2 | class FenwickTree: |
| 3 | |
| 4 | def __init__(self, SIZE): # create fenwick tree with size SIZE |
| 5 | self.Size = SIZE |
| 6 | self.ft = [0 for i in range (0,SIZE)] |
| 7 | |
| 8 | def update(self, i, val): # update data (adding) in index i in O(lg N) |
| 9 | while (i < self.Size): |
| 10 | self.ft[i] += val |
| 11 | i += i & (-i) |
| 12 | |
| 13 | def query(self, i): # query cumulative data from index 0 to i in O(lg N) |
| 14 | ret = 0 |
| 15 | while (i > 0): |
| 16 | ret += self.ft[i] |
| 17 | i -= i & (-i) |
| 18 | return ret |
| 19 | |
| 20 | if __name__ == '__main__': |
| 21 | f = FenwickTree(100) |