Prefix sum of all elements in [0, right) in O(lg N) Parameters: right (int): right bound of the query (exclusive) Returns: int: sum of all elements in [0, right) >>> a = [i for i in range(128)] >>> f = FenwickTree(a) >>> res
(self, right: int)
| 127 | self.add(index, value - self.get(index)) |
| 128 | |
| 129 | def prefix(self, right: int) -> int: |
| 130 | """ |
| 131 | Prefix sum of all elements in [0, right) in O(lg N) |
| 132 | |
| 133 | Parameters: |
| 134 | right (int): right bound of the query (exclusive) |
| 135 | |
| 136 | Returns: |
| 137 | int: sum of all elements in [0, right) |
| 138 | |
| 139 | >>> a = [i for i in range(128)] |
| 140 | >>> f = FenwickTree(a) |
| 141 | >>> res = True |
| 142 | >>> for i in range(len(a)): |
| 143 | ... res = res and f.prefix(i) == sum(a[:i]) |
| 144 | >>> res |
| 145 | True |
| 146 | """ |
| 147 | if right == 0: |
| 148 | return 0 |
| 149 | result = self.tree[0] |
| 150 | right -= 1 # make right inclusive |
| 151 | while right > 0: |
| 152 | result += self.tree[right] |
| 153 | right = self.prev(right) |
| 154 | return result |
| 155 | |
| 156 | def query(self, left: int, right: int) -> int: |
| 157 | """ |