3 Fenwick Tree Analysis and Implementation Solve the following exercises. Let F be the Fenwick tree...

Transcribed Image Text:

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. 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.

Answer rating: 100% (QA)

33 j i and i 1 Here i means the ones complement of a i so basically i1 is the twos complement of i n... View the full answer