Add a value to index in O(lg N) Parameters: index (int): index to add value to value (int): value to add to index Returns: None >>> f = FenwickTree([1, 2, 3, 4, 5]) >>> f.add(0, 1) >>> f.add(1, 2) >>> f.a
(self, index: int, value: int)
| 78 | return index - (index & (-index)) |
| 79 | |
| 80 | def add(self, index: int, value: int) -> None: |
| 81 | """ |
| 82 | Add a value to index in O(lg N) |
| 83 | |
| 84 | Parameters: |
| 85 | index (int): index to add value to |
| 86 | value (int): value to add to index |
| 87 | |
| 88 | Returns: |
| 89 | None |
| 90 | |
| 91 | >>> f = FenwickTree([1, 2, 3, 4, 5]) |
| 92 | >>> f.add(0, 1) |
| 93 | >>> f.add(1, 2) |
| 94 | >>> f.add(2, 3) |
| 95 | >>> f.add(3, 4) |
| 96 | >>> f.add(4, 5) |
| 97 | >>> f.get_array() |
| 98 | [2, 4, 6, 8, 10] |
| 99 | """ |
| 100 | if index == 0: |
| 101 | self.tree[0] += value |
| 102 | return |
| 103 | while index < self.size: |
| 104 | self.tree[index] += value |
| 105 | index = self.next_(index) |
| 106 | |
| 107 | def update(self, index: int, value: int) -> None: |
| 108 | """ |