Chris recently received an array p as his birthday gift from Joseph, whose elements are either 0 or 1. He wants to use it to gen
erate an infinite long superarray. Here is his strategy: each time, he inverts his array by bits, changing all 0 to 1 and all 1 to 0 to get another array, then concatenate the original array and the inverted array together. For example, if the original array is [0,1,1,0] then the inverted array will be [1,0,0,1] and the new array will be [0,1,1,0,1,0,0,1]. He wonders what the array will look like after he repeat this many many times.
He ask you to help him sort this out. Given the original array pp of length ????n and two indices a,b (????≪????≪????, means much less than) Design an algorithm to calculate the sum of elements between a and b of the generated infinite array p^, specifically, ∑????≤????≤????p????^. He also wants you to do it real fast, so make sure your algorithm runs less than O(b) time. Explain your algorithm and analyze its complexity.
