每日一题：2的幂数组中查询范围内的乘积；快速幂算法

题目选自2438. 二的幂数组中查询范围内的乘积

还是一样的，先讲解思路，然后再说代码。

题目有一定难度，所以我要争取使所有人都能看懂，用的方法会用最常规的思想。关于语言，都是互通的，只要你懂了一门语言，可以做到尽量理解其他语言。

每一次头脑风暴都是一次十足的成长，请有耐心，即使是小白，看完自有收获。

这道题跟之前那道题目重新排序得到 2 的幂呼应起来了，没有看过的可以先去看一下前面那道题。

题目

给你一个正整数 n ，你需要找到一个下标从 0 开始的数组 powers ，它包含最少数目的 2 的幂，且它们的和为 n 。powers 数组是 非递减 顺序的。根据前面描述，构造 powers 数组的方法是唯一的。

同时给你一个下标从 0 开始的二维整数数组 queries ，其中 queries[i] = [lefti, righti] ，其中 queries[i] 表示请你求出满足 lefti <= j <= righti 的所有 powers[j] 的乘积。

请你返回一个数组 answers ，长度与 queries 的长度相同，其中 answers[i]是第 i 个查询的答案。由于查询的结果可能非常大，请你将每个 answers[i] 都对 10^9 + 7 取余。

示例

示例 1：

输入：n = 15, queries = [[0,1],[2,2],[0,3]]
输出：[2,4,64]
解释：
对于 n = 15 ，得到 powers = [1,2,4,8] 。没法得到元素数目更少的数组。
第 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 。
每个答案对 109 + 7 取余得到的结果都相同，所以返回 [2,4,64] 。

示例 2：

输入：n = 2, queries = [[0,0]]
输出：[2]
解释：
对于 n = 2, powers = [2] 。
唯一一个查询的答案是 powers[0] = 2 。答案对 109 + 7 取余后结果相同，所以返回 [2] 。

题目解析

（题目意思很简单，但是给这个题目做翻译的人翻译的很差劲，所以得重新译一遍）

给你一个正整数 n，你需要找到一个数组 powers。这个数组包含若干个 2 的幂（比如 1, 2, 4, 8, 16...），它们加起来正好等于 n。并且，powers 数组要用最少数量的 2 的幂，同时数组里的数必须是从小到大排列的（非递减）。题目保证这种找法是唯一的。

然后，你还得到一个二维数组 queries，里面每个元素是 [left, right]。对于每一个 [left, right]，你需要计算 powers 数组中从 left下标到 right下标（包含两端）的所有数字的乘积。

最后，因为乘积可能会非常大，所以你计算出来的每个乘积都要对 10^9 + 7 取余。最后把所有查询的结果放在一个数组里返回。

1.题目与“2的幂”关联

这个正整数n是这个数组相加起来的结果，很容易想到每一个数都有它相对应的二进制数。

例如，数字 13。它的二进制是 1101

2.powers数组是由2的幂组成的

每一个数都有它相对应的唯一二进制数，我们只需要把在 n 的二进制表示中出现的那些 2^k 找出来，然后按从小到大的顺序排列就行了

比如 n = 15，二进制是 1111，表示 15 = 8+4+2+1 = 2^3 + 2^2 + 2^1 + 2^0，所以 powers = [1, 2, 4, 8]。
比如 n = 12，二进制是 1100，表示 12 = 2^3 + 2^2，所以 powers = [4, 8]。

3.如何处理查询 `queries？`

1.对于每个 [left, right]，计算 powers[left] * powers[left+1] * ... * powers[right] 对 10^9 + 7取余。

我们可以写一个循环，从 left 遍历到 right，把每个 powers[j] 乘起来，每乘一次就取余。

# 伪代码
product = 1
for j from left to right:product = (product * powers[j]) % MOD

2.如果 queries 很多，或者 right - left 的距离很大，上面的循环可能会有点慢。有没有更快的办法？

所以我们需要利用指数的性质：2^a * 2^b = 2^(a+b)。

也就是说，我们可以把 powers 数组中的每个元素看成是 2 的某个次方，计算乘积时只需要把这些次方加起来，然后再计算 2 的这个总次方。比如 powers = [1, 2, 4, 8]，其实是 [2^0, 2^1, 2^2, 2^3]，查询 [0, 2] 的乘积是 2^0 * 2^1 * 2^2 = 2^(0+1+2) = 2^3 = 8。

这样可以避免直接计算大数。

4.如何快速计算 `2` 的高次方并取模？

我们需要计算 2^x mod (10^9 + 7)，其中 x 可能很大。
直接用 2^x 会溢出，所以需要用到快速幂算法

快速幂的核心思想是把指数表示成二进制形式，每次只处理一位。（后面代码解析会详细说明语法）

完整代码

class Solution(object):def productQueries(self, n, queries):""":type n: int:type queries: List[List[int]]:rtype: List[int]"""MOD = 10**9 + 7# 第一步：把 n 表示成 2 的幂的和，得到 powers 数组powers = []power = 0while n > 0:if n & 1:  # 如果 n 的最低位是 1powers.append(1 << power)  # 加入 2^powern >>= 1  # n 右移一位power += 1# 第二步：把 powers 数组中的每个元素表示成 2 的指数# 比如 powers = [1, 2, 4, 8] 表示成 exponents = [0, 1, 2, 3]exponents = []for p in powers:exp = 0while (1 << exp) != p:exp += 1exponents.append(exp)# 第三步：快速幂算法，计算 2^x mod MODdef quick_pow(base, exp, mod):if exp == 0:return 1result = 1base %= modwhile exp > 0:if exp & 1:  # 如果 exp 的最低位是 1result = (result * base) % modbase = (base * base) % modexp >>= 1return result# 第四步：处理每个查询answers = []for left, right in queries:# 计算范围内所有指数的和total_exp = sum(exponents[left:right + 1])# 用快速幂计算 2^total_exp mod MODresult = quick_pow(2, total_exp, MOD)answers.append(result)return answers

代码解析

代码结构

代码分为四个主要部分：

把 n 表示成 2 的幂的和，得到 powers 数组。
把 powers 数组中的每个元素表示成 2 的指数，得到 exponents 数组。
实现快速幂算法，用于计算 2^x mod MOD。
处理每个查询，计算答案。

详细解析

第一部分：得到 powers 数组
```
powers = []
power = 0
while n > 0:if n & 1:  # 如果 n 的最低位是 1powers.append(1 << power)  # 加入 2^powern >>= 1  # n 右移一位power += 1
```
- 这一部分的作用是把 n 表示成 2 的幂的和。
- n & 1 是位运算，检查 n 的最低位是否为 1。如果是 1，说明需要加入 2^power。
- 1 << power 是位运算，表示 2^power。
- n >>= 1 是位运算，把 n 右移一位，相当于除以 2。
- 比如 n = 15，二进制是 1111，循环过程如下：
  - 第一轮：n = 1111，最低位是 1，加入 2^0 = 1，n 右移变成 111。
  - 第二轮：n = 111，最低位是 1，加入 2^1 = 2，n 右移变成 11。
  - 第三轮：n = 11，最低位是 1，加入 2^2 = 4，n 右移变成 1。
  - 第四轮：n = 1，最低位是 1，加入 2^3 = 8，n 右移变成 0。
  - 结束，得到 powers = [1, 2, 4, 8]。
第二部分：得到 exponents 数组
```
exponents = []
for p in powers:exp = 0while (1 << exp) != p:exp += 1exponents.append(exp)
```
- 这一部分的作用是把 powers 数组中的每个元素表示成 2 的指数。
- 比如 powers = [1, 2, 4, 8]，我们需要得到 exponents = [0, 1, 2, 3]，因为 1 = 2^0, 2 = 2^1, 4 = 2^2, 8 = 2^3。
- 对于每个 p，我们用一个循环找到 exp，使得 2^exp == p。
第三部分：快速幂算法
```
def quick_pow(base, exp, mod):if exp == 0:return 1result = 1base %= modwhile exp > 0:if exp & 1:  # 如果 exp 的最低位是 1result = (result * base) % modbase = (base * base) % modexp >>= 1return result
```
- 这一部分的作用是快速计算 base^exp mod mod。
- 直接计算 base^exp 可能会导致数字非常大（比如 2^100），所以我们用快速幂算法。
- 快速幂的核心思想是把指数 exp 表示成二进制形式，每次只处理一位。
- 比如要计算 2^10 mod 1000000007：
  - 10 的二进制是 1010。
  - 从低位到高位处理：
    - 第 0 位是 0，不用乘。
    - 第 1 位是 1，乘上 2^2。
    - 第 2 位是 0，不用乘。
    - 第 3 位是 1，乘上 2^8。
  - 每次处理时，base 都会平方（base = base * base），这样可以快速得到高次方的值。
  - 每次乘法后都对 mod 取模，避免数字过大。
第四部分：处理查询
```
answers = []
for left, right in queries:# 计算范围内所有指数的和total_exp = sum(exponents[left:right + 1])# 用快速幂计算 2^total_exp mod MODresult = quick_pow(2, total_exp, MOD)answers.append(result)
```
- 这一部分的作用是处理每个查询。
- 对于每个查询 [left, right]，我们需要计算 powers[left] * powers[left+1] * ... * powers[right]。
- 因为 powers 中的每个元素是 2 的某个次方，所以乘积可以表示成 2 的指数之和。
- 比如 powers = [1, 2, 4, 8]，exponents = [0, 1, 2, 3]，查询 [0, 2]：
  - 取出 exponents[0:3] = [0, 1, 2]。
  - 计算指数之和：0 + 1 + 2 = 3。
  - 计算 2^3 mod 1000000007 = 8。
  - 答案是 8。
- 最后把所有答案存入 answers 数组。

时间复杂度

第一部分：得到 powers 数组
- 我们用一个 while 循环处理 n，每次把 n 右移一位，直到 n 变成 0。
- n 的二进制表示有 log n 位（因为 2 的多少次方可以表示 n）。
- 所以这一部分的时间复杂度是 O(log n)。
第二部分：得到 exponents 数组
- 对于 powers 数组中的每个元素 p，我们用一个 while 循环找到对应的指数 exp。
- powers 数组的长度最多是 log n（因为 n 的二进制表示最多有 log n 位 1）。
- 对于每个 p，找到 exp 的循环次数最多是 log p，而 p 最大是 n，所以最坏情况下是 O(log n)。
- 总的时间复杂度是 O(log n * log n)，但实际上 p 的值是递增的，平均复杂度更低。
第三部分：快速幂算法
- 快速幂算法的时间复杂度是 O(log exp)，因为我们把指数 exp 表示成二进制形式，每次处理一位。
- 在我们的题目中，exp 是指数之和，最坏情况下可能是 O(log n) 级别的（因为 n 本身是 2 的幂的和）。
第四部分：处理查询
- 假设有 q 个查询（q 是 queries 的长度）。
- 对于每个查询，我们需要计算范围内指数的和，时间复杂度是 O(log n)（因为 powers 数组的长度最多是 log n）。
- 然后用快速幂计算结果，时间复杂度是 O(log exp)，其中 exp 最坏情况下是 O(log n)。
- 所以每个查询的复杂度是 O(log n)。
- 总的时间复杂度是 O(q * log n)。