Fenwick inversions

Questions 1 to 5 of 7

1. 1. What does this program print? ``python tree = [0] * 9 def add(position, delta): i = position while i <= 8: tree[i] += delta i += i & -i def prefix_sum(position): total = 0 i = position while i > 0: total += tree[i] i -= i & -i return total add(5, 1) add(3, 1) print(prefix_sum(7)) print(prefix_sum(4)) print(tree[6]) ``

   2, 1, 02, 1, 11, 1, 12, 2, 1
2. 2. What does this program print? ``python from bisect import bisect_left tree = [0] * 5 def add(position, delta): i = position while i <= 3: tree[i] += delta i += i & -i def prefix_sum(position): total = 0 i = position while i > 0: total += tree[i] i -= i & -i return total def count_inversions(values): sorted_values = sorted(set(values)) inversions = 0 seen = 0 for v in values: rank = bisect_left(sorted_values, v) + 1 add(rank, 1) not_greater = prefix_sum(rank) inversions += seen - not_greater seen += 1 return inversions print(f"inversions: {count_inversions([1, 2, 3])}") ``

   inversions: 0inversions: 3inversions: 2inversions: -3
3. 3. Which statements about the inversion count in this lesson are true? Pick all that apply.

   Pick every answer that is true.

   Two equal values are not counted as an inversionA value's rank is its place in the sorted list of distinct values, counted from 1The query for earlier values less than or equal to x must run before x is added to the treeA Python int has no fixed size, so the inversion count of a 100000-value array cannot overflowPython needs a separate 64-bit integer type for big counts, or the count wraps around at 2 to the power 63
4. 4. In a Fenwick tree of size 8, which cells does add(5, 1) change, in order?

   5, 6, 85, 6, 7, 85, 4, 85, 10
5. 5. The array 5 4 3 2 1 has every pair out of order. How many inversions does a reversed array of 100000 values have?

   10000021474836474999950000499995000