3 Fenwick Tree Analysis and Implementation Solve the following exercises. Let F be the Fenwick tree of an array A of length n. 3.1 Discuss why the array F is called a tree. 3.2 Show that any interval [1, i] is covered by O(logn) partial sums stored in F. 3.3 Consider the index computation for sum. Let i be a positive integer whose rightmost 1-bit is at position k, i.e., if i = 10 = 1010 then k = 1 and 2 = 2 = 2. Show that j =i&i + 1 is the integer 2k. Here i the bitwise negation of i, i.e., if i = 10 then i = 01012. 3.4 Write the pseudocode for sum and update. Hint: use exercise 3.3.