Initialize the Fenwick tree with arr in O(N) Parameters: arr (list): list of elements to initialize the tree with Returns: None >>> a = [1, 2, 3, 4, 5] >>> f1 = FenwickTree(a) >>> f2 = FenwickTree(size=len(a)) >>> fo
(self, arr: list[int])
| 26 | raise ValueError("Either arr or size must be specified") |
| 27 | |
| 28 | def init(self, arr: list[int]) -> None: |
| 29 | """ |
| 30 | Initialize the Fenwick tree with arr in O(N) |
| 31 | |
| 32 | Parameters: |
| 33 | arr (list): list of elements to initialize the tree with |
| 34 | |
| 35 | Returns: |
| 36 | None |
| 37 | |
| 38 | >>> a = [1, 2, 3, 4, 5] |
| 39 | >>> f1 = FenwickTree(a) |
| 40 | >>> f2 = FenwickTree(size=len(a)) |
| 41 | >>> for index, value in enumerate(a): |
| 42 | ... f2.add(index, value) |
| 43 | >>> f1.tree == f2.tree |
| 44 | True |
| 45 | """ |
| 46 | self.size = len(arr) |
| 47 | self.tree = deepcopy(arr) |
| 48 | for i in range(1, self.size): |
| 49 | j = self.next_(i) |
| 50 | if j < self.size: |
| 51 | self.tree[j] += self.tree[i] |
| 52 | |
| 53 | def get_array(self) -> list[int]: |
| 54 | """ |