主題
題目連結(jié)：
題目意譯：
給定一正整數(shù) n，現(xiàn)在存在一個索引值從 0 開始之陣列 powers，其由總和為 n 的最少個 2 之冪次所組成。該陣列由非遞減之順序而排列，而且只有一個方式可以形成該陣列。
你同時也給定一個索引值從 0 開始的二維陣列 queries，其中 queries[i] = [lefti, righti]。每個 queries[i] 代表著一筆詢問，其中你需要找到所有 powers[j] 之乘積，其中 lefti ≦ j ≦ righti。
回傳一陣列 answers，長度等於 queries，其中 answers[i] 為第 i 筆詢問的答案。由於答案可能很大，每個 answers[i] 應(yīng)先模 10 ^ 9 + 7 後再回傳。
限制：
1 ≦ n ≦ 10 ^ 9
1 ≦ queries.length ≦ 10 ^ 5
0 ≦ starti ≦ endi < powers.length
範(fàn)例測資：
範(fàn)例 1：
輸入： n = 15, queries = [[0,1],[2,2],[0,3]]
輸出： [2,4,64]
解釋：
對於 n = 15，powers = [1,2,4,8]。可以證明 powers 之大小無法再小了。
第 1 筆詢問的答案：powers[0] × powers[1] = 1 × 2 = 2。
第 2 筆詢問的答案：powers[2] = 4。
第 3 筆詢問的答案：powers[0] × powers[1] × powers[2] × powers[3] = 1 × 2 × 4 × 8 = 64。
每個答案模 10 ^ 9 + 7 後都是一樣的數(shù)值，所以回傳 [2,4,64]。
範(fàn)例 2：
輸入： n = 2, queries = [[0,0]]
輸出： [2]
解釋：
對於 n = 2，powers = [2]。
唯一一筆詢問的答案為 powers[0] = 2。答案模 10 ^ 9 + 7 後是一樣的數(shù)值，所以回傳 [2]。
解題思維：
其實題目形容的 powers，即為 n 的二進位制。所以我們把 n 轉(zhuǎn)成二進位然後把每一個 2 的冪次丟進一個陣列即為 powers。
可以看到 powers 的大小最大為 30。因此對於每一筆詢問直接掃過對應(yīng)的項次並相乘（記得模 10 ^ 9 + 7）即可。
不過範(fàn)例程式碼在建 powers 是存冪次之值本身（例如說對於 2 ^ x，存的是 x 而不是 2 ^ x），然後建立其前綴和（Prefix Sums，如這題），以便快速求得任意區(qū)間總和。
而求得冪次總和之後，要轉(zhuǎn)回到實際的數(shù)值（即 2 ^ x 之形式），而這可以用快速冪（如這題）得到。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
