二的幂数组中查询范围内的乘积

标签: 位运算 数组 前缀和

难度: Medium

给你一个正整数 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] 都对 109 + 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] 。

提示：

  • 1 <= n <= 109
  • 1 <= queries.length <= 105
  • 0 <= starti <= endi < powers.length

Submission

运行时间: 97 ms

内存: 42.1 MB

MOD = 10 ** 9 + 7

class Solution:
    def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:
        power = []
        while n:
            lb = n & -n
            power.append(lb)
            n ^= lb # <=> n &= n-1
        pn = len(power)
        res = [[0] * pn for _ in range(pn)]
        for i in range(pn):
            res[i][i] = power[i]
            for j in range(i + 1, pn):
                res[i][j] = (res[i][j-1] * power[j]) % MOD
        return [res[l][r] for l, r in queries]

Explain

题解的思路是首先找出n的二进制表示中所有的1所对应的幂，将这些幂存入power数组中。接着，构建一个二维数组res，用于存储所有可能的查询区间[l, r]内的幂的乘积。最后，对于每个查询，直接从res数组中取出对应的结果。

时间复杂度: O((log n)^2 + q)

空间复杂度: O((log n)^2)

MOD = 10 ** 9 + 7

class Solution:
    def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:
        power = [] # 存储n的二进制表示中所有1对应的幂
        while n:
            lb = n & -n # 找到n的最低位的1对应的幂
            power.append(lb)
            n ^= lb # 去掉n的最低位的1
        pn = len(power)
        res = [[0] * pn for _ in range(pn)] # 存储所有可能的查询区间内的幂的乘积
        for i in range(pn):
            res[i][i] = power[i]
            for j in range(i + 1, pn):
                res[i][j] = (res[i][j-1] * power[j]) % MOD # 计算区间[i, j]内的幂的乘积
        return [res[l][r] for l, r in queries] # 返回所有查询的结果

Explore

在二进制中，一个数n的表示包含了这个数由2的幂次相加而成的具体信息。例如，n=5在二进制中表示为101，这意味着它可以表示为2^0 + 2^2。使用二进制表示中1的位置对应的幂可以直接得到组成n的2的幂次，这是针对具体数n的优化存储方式。与直接生成2的幂次方列表不同，这种方法只生成那些实际上在数n的二进制表示中出现的幂次，从而节省空间并直接定位到相关幂次，避免不必要的计算和存储。

确实，构建res数组来存储所有可能的查询区间[l, r]内的幂的乘积可能会导致内存效率低下，尤其是当n较大时。由于res是一个二维数组，其大小为幂次数组长度的平方，因此当幂数组长度较大时，所需的存储空间会快速增加。对于大规模数据或更长的幂次链，这种方法会占用大量内存，可能导致内存溢出或性能问题。在实际应用中，可能需要考虑更高效的数据结构或算法，如使用线段树或者懒惰传播等技术进行优化。

题解中使用取模操作的主要原因是为了防止整数溢出和保持计算结果的稳定性。由于连乘的结果可能非常大，超过了常规整型变量可以存储的范围，因此使用取模操作来确保结果不会溢出并且能够保持在一个安全的数值范围内。取模操作也确保了结果符合题目设定的约束条件（例如MOD = 10**9 + 7），这是编程竞赛和算法实现中常用的技术，用以处理大数的乘法运算问题。