Get the Normal Array of the Fenwick tree in O(N) Returns: list: Normal Array of the Fenwick tree >>> a = [i for i in range(128)] >>> f = FenwickTree(a) >>> f.get_array() == a True
(self)
| 51 | self.tree[j] += self.tree[i] |
| 52 | |
| 53 | def get_array(self) -> list[int]: |
| 54 | """ |
| 55 | Get the Normal Array of the Fenwick tree in O(N) |
| 56 | |
| 57 | Returns: |
| 58 | list: Normal Array of the Fenwick tree |
| 59 | |
| 60 | >>> a = [i for i in range(128)] |
| 61 | >>> f = FenwickTree(a) |
| 62 | >>> f.get_array() == a |
| 63 | True |
| 64 | """ |
| 65 | arr = self.tree[:] |
| 66 | for i in range(self.size - 1, 0, -1): |
| 67 | j = self.next_(i) |
| 68 | if j < self.size: |
| 69 | arr[j] -= arr[i] |
| 70 | return arr |
| 71 | |
| 72 | @staticmethod |
| 73 | def next_(index: int) -> int: |