Query the sum of all elements in [left, right) in O(lg N) Parameters: left (int): left bound of the query (inclusive) right (int): right bound of the query (exclusive) Returns: int: sum of all elements in [left, right) >>> a = [
(self, left: int, right: int)
| 154 | return result |
| 155 | |
| 156 | def query(self, left: int, right: int) -> int: |
| 157 | """ |
| 158 | Query the sum of all elements in [left, right) in O(lg N) |
| 159 | |
| 160 | Parameters: |
| 161 | left (int): left bound of the query (inclusive) |
| 162 | right (int): right bound of the query (exclusive) |
| 163 | |
| 164 | Returns: |
| 165 | int: sum of all elements in [left, right) |
| 166 | |
| 167 | >>> a = [i for i in range(128)] |
| 168 | >>> f = FenwickTree(a) |
| 169 | >>> res = True |
| 170 | >>> for i in range(len(a)): |
| 171 | ... for j in range(i + 1, len(a)): |
| 172 | ... res = res and f.query(i, j) == sum(a[i:j]) |
| 173 | >>> res |
| 174 | True |
| 175 | """ |
| 176 | return self.prefix(right) - self.prefix(left) |
| 177 | |
| 178 | def get(self, index: int) -> int: |
| 179 | """ |