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 generate 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 (≪≪,≪(n≪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^∑a≤i≤bpi^. He also wants you to do it real fast, so make sure your algorithm runs less than ()O(b) time.

Required:
Explain your algorithm and analyze its complexity.