Given an array of integers, arr, you need to create a new array, arr', by performing a number of operations. Since arr may be large, you want to choose a data structure that will provide optimal performance. Choose the best data structure.

Note: The array is $1-$indexed. All positive integers can be represented as the sum of powers of $2.$

For each index i that is a power of $2$: Replace arr'$[$i$]$ with the sum of the values in arr from index $1$ through i$.$ For example, if i $=2,$ the new arr' $=[1,2,3],$ then arr'$[2]=$ arr$[1]+$ arr$[2].$ Since $2$ is a power of $2,$ arr'$[2]=$ arr$[1]+$ arr$[2].$

For each index i that is even but not a power of $2$: Replace arr'$[$i$]$ with arr'$[$k$1]+$ arr'$[$k$2]+...+$ arr'$[$km$],$ where the k values are the powers of $2$ that sum to i$.$ If i $=6,$ arr'$[6]=$ arr'$[2]+$ arr'$[4].$

For each index i that is odd: The value of arr'$[$i$]$ should be unchanged.

Examples:

arr $=[1,1,1,1,1,1,1,1]$

Output: arr' $=[1,2,1,4,1,6,1,8]$

arr $=[1,2,3,4,5,6,7,8]$

Output: arr' $=[1,3,3,10,5,11,7,36]$

Pick ONE option:

Create an array and do a prefix sum of all even index elements per the rules.

Implement a binary index tree and update all the even indexes per the rules.

Design a segment tree. For even indexes, find the powers of $2$ that sum to the index and sum the values at those indexes. Save the value to its node.

Create an array. For each even index, iterate the array to determine final values.