2438.二的幂数组中查询范围内的乘积：模拟(前缀和可选)

【LetMeFly】2438.二的幂数组中查询范围内的乘积：模拟(前缀和可选)

力扣题目链接：https://leetcode.cn/problems/range-product-queries-of-powers/

给你一个正整数 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

解题方法：模拟

如何将$n$拆成递增的2的幂组成的数组powers

很简单，$n$二进制下哪一位(记为$i$)是$1$就将$1\lt \lt i$按顺序加入powers数组。

对于一个query如何求出对应answer

两种方法：

1. 直接暴力从query[0]累乘到query[1]并随时取模
2. 前缀和的思想，使用数组perfix[j]代表$\prod_{0}^{j-1}powers[i]$

直接暴力的方法并不会很耗时，因为powers数组中最多30个元素；

前缀和的思想适用于Python这种自带大整数的编程语言，否则取模后的相除还需要取逆元。

时空复杂度分析

暴力：

• 时间复杂度$O(\log n\times len(queries))$
• 空间复杂度$O(\log n)$

前缀和

• 时间复杂度$O(\log n + len(queries))$
• 空间复杂度$O(\log n)$

AC代码

C++

/*
 * @Author: LetMeFly
 * @Date: 2025-08-11 18:41:58
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-08-11 21:43:41
 */
typedef long long ll;
const ll MOD = 1e9 + 7;

class Solution {
public:
    vector<int> productQueries(int n, vector<vector<int>>& queries) {
        vector<int> pows;
        int th = 0;
        while (n) {
            if (n & 1) {
                pows.push_back(1 << th);
            }
            n >>= 1;
            th++;
        }
        vector<int> ans(queries.size());
        for (int i = 0; i < queries.size(); i++) {
            ll thisVal = 1;
            for (int j = queries[i][0]; j <= queries[i][1]; j++) {
                thisVal = thisVal * pows[j] % MOD;
            }
            ans[i] = thisVal;
        }
        return ans;
    }
};

Python

'''
Author: LetMeFly
Date: 2025-08-11 21:37:10
LastEditors: LetMeFly.xyz
LastEditTime: 2025-08-11 21:46:52
'''
from typing import List

class Solution:
    def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:
        pows = []
        th = 0
        while n:
            if n & 1:
                pows.append(1 << th)
            th += 1
            n >>= 1
        perfix = [1] * (len(pows) + 1)
        for i in range(1, len(pows) + 1):
            perfix[i] = perfix[i - 1] * pows[i - 1]
        return [perfix[q[1] + 1] // perfix[q[0]] % 1000000007 for q in queries]

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源