题目

给你一个正整数 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 。 每个答案对 10^9 + 7 取余得到的结果都相同，所以返回 [2,4,64] 。

示例 2：

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

提示：

• 1 <= n <= 10^9
• 1 <= queries.length <= 10^5
• 0 <= start_i <= end_i < powers.length

解题思路

1.理解 powers 数组的构成

题目要求我们找到一个包含最少数目的 2 的幂的数组 powers，使得它们的和等于 n。

这个描述其实就是整数的二进制表示。任何一个正整数 n 都可以唯一地表示为其二进制形式，也就是若干个 2 的幂的和。例如：

• n = 15
  • 二进制表示是 1111₂
  • 15 = 8 + 4 + 2 + 1 = 2³ + 2² + 2¹ + 2⁰
  • 因此，powers 数组就是 [2⁰, 2¹, 2², 2³]，即 [1, 2, 4, 8]。
• n = 13
  • 二进制表示是 1101₂
  • 13 = 8 + 4 + 1 = 2³ + 2² + 2⁰
  • 因此，powers 数组就是 [2⁰, 2², 2³]，即 [1, 4, 8]。

这是构成 powers 数组的唯一且最优（元素最少）的方法。我们可以通过一个循环来找出 n 的二进制表示中所有为 "1" 的位。从第 0 位开始检查，如果第 i 位是 "1"，就意味着 2ⁱ 是 powers 数组的一个元素。

# 伪代码
n = 15
powers = []
for i in range(31): # n <= 10^9，所以最多到 2^30 左右
    if (n >> i) & 1: # 检查 n 的第 i 位是否为 1
        powers.append(2**i)

2.乘积变加法

现在我们需要计算 queries[i] = [left, right] 区间内 powers 数组元素的乘积。

powers 数组的元素都是 2 的幂，例如 [2^p₀, 2^p₁, 2^p₂, ...]。 那么区间的乘积就是： powers[left] * powers[left+1] * ... * powers[right] = 2^p_{left} * 2^p_{left+1} * ... * 2^p_{right}

根据指数运算法则 a^m * a^n = a^(m+n)，上面的乘积可以转化为： = 2^(p_{left} + p_{left+1} + ... + p_{right})

这个转化是解题的关键！ 它把一个区间乘积问题，转化成了一个对指数的区间求和问题。计算 2 的大次幂远比直接连乘再取模要方便和安全。

所以，我们实际上不需要 powers 数组本身，而是需要一个由这些幂的指数组成的数组。我们称之为 exponents 数组。

• 对于 n = 15，powers = [1, 2, 4, 8] = [2⁰, 2¹, 2², 2³]。exponents 数组就是 [0, 1, 2, 3]。
• 对于 n = 13，powers = [1, 4, 8] = [2⁰, 2², 2³]。exponents 数组就是 [0, 2, 3]。

现在，对于每个查询 [left, right]，我们的任务变成了：

1. 计算指数和：S = exponents[left] + exponents[left+1] + ... + exponents[right]
2. 计算最终结果： (2^S) mod (10⁹ + 7)

前缀和计算区间

对于大量的区间求和查询，最经典和高效的方法是使用前缀和 (Prefix Sum)。

我们可以先预处理 exponents 数组，计算出它的前缀和数组 prefix_sums。 prefix_sums[i] 表示 exponents 数组前 i 个元素的和（即 exponents[0] + ... + exponents[i-1]）。

• prefix_sums[0] = 0
• prefix_sums[1] = exponents[0]
• prefix_sums[2] = exponents[0] + exponents[1]
• ...
• prefix_sums[i] = prefix_sums[i-1] + exponents[i-1]

有了前缀和数组，计算任意区间 [left, right] 的和就变成了 O(1) 的操作： sum(exponents[left]...exponents[right]) = prefix_sums[right+1] - prefix_sums[left]

快速幂计算结果

得到指数和 S 之后，我们需要计算 2^S mod (10⁹ + 7)。 由于 S 可能非常大，直接计算 2^S 会导致溢出。这里需要使用模幂运算（Modular Exponentiation），通常通过快速幂算法来实现。几乎所有编程语言的标准库或常用库中都有这个功能（例如 Python 的 pow(2, S, MOD)）。

在C++中，快速幂算法需要自己构造，具体如下：

算法流程

1. 构造指数数组 exponents:
   • 创建一个空数组 exponents。
   • 遍历 i 从 0 到 30。
   • 检查 n 的二进制表示的第 i 位。如果为 "1" ((n >> i) & 1 == 1)，则将 i 添加到 exponents 数组中。
2. 计算前缀和数组 prefix_sums:
   • 获取 exponents 数组的长度 L。
   • 创建一个长度为 L+1 的前缀和数组 prefix_sums，并初始化为 0。
   • 遍历 i 从 0 到 L-1，计算 prefix_sums[i+1] = prefix_sums[i] + exponents[i]。
3. 处理查询:
   • 创建一个空数组 answers 用于存放结果。
   • 定义模数 MOD = 10⁹ + 7。
   • 对于每一个查询 [left, right]： a. 使用前缀和数组计算指数总和：total_exponent = prefix_sums[right+1] - prefix_sums[left]。 b. 使用快速幂算法计算 result = pow(2, total_exponent, MOD)。 c. 将 result 添加到 answers 数组中。
4. 返回 answers 数组。

复杂度分析

• 时间复杂度:
  • 构造 exponents 数组：n 最大为 10⁹，小于 2³⁰，所以循环大约 30 次。复杂度为 $O(log n)$。
  • 计算 prefix_sums：exponents 数组的长度最多为 30。复杂度为 $O(log n)$。
  • 处理所有查询：如果有 q 个查询，每个查询的计算是 O(1)（查前缀和表）+ $O(log(exponent_sum))$（快速幂）。由于指数和最大约为 30*30 = 900，所以快速幂非常快。总查询时间为 $O(q * log(exponent_sum))$，可以近似看作 $O(q)$。
  • **总时间复杂度为 $O(log n + q)$。
• 空间复杂度:
  • exponents 数组和 prefix_sums 数组的空间都是 $O(log n)$。
  • answers 数组的空间是 O(q)。
  • 总空间复杂度为 $O(log n + q)。

快速幂算法

“快速幂”，又称“二进制取幂 (Binary Exponentiation)”。它的核心思想就藏在“二进制”这个词里。假设我们要计算 3^13。最直观的方法是什么？就是一个一个地乘： 3 * 3 * 3 * 3 * 3 * 3 * 3 * 3 * 3 * 3 * 3 * 3 * 3 (总共乘了12次)

如果我们要计算 a^b，这个方法需要循环 b-1 次。当 b 非常大（比如 10⁹）时，计算机会直接“超时”，因为它要算几十亿次。

让我们再次回到 3^13。数学上有一个基本规律：a^(m+n) = a^m * a^n。 我们可以利用这个规律来做点文章。

1. 把指数 13 写成二进制。 13 的二进制是 1101₂。
2. 把二进制翻译成十进制的“幂之和”。 1101₂ 从右到左分别代表 2⁰, 2¹, 2², 2³ 的权重。 所以 13 = 1*8 + 1*4 + 0*2 + 1*1 = 8 + 4 + 1。
3. 代入原式。 3^13 = 3^(8 + 4 + 1)
4. 利用公式 a^(m+n) = a^m * a^n 拆开。 3^13 = 3^8 * 3^4 * 3^1

我们把“计算13个3的乘积”变成了“计算 3^1、3^4、3^8 这三项的乘积”。乘法次数大大减少了。

但是，我们怎么快速得到 3^1, 3^4, 3^8 这些项呢？观察一下这些项：3^1, 3^2, 3^4, 3^8, 3^16... 会发现一个规律：

• 3^2 = (3^1) * (3^1)
• 3^4 = (3^2) * (3^2)
• 3^8 = (3^4) * (3^4)
• ...
• a^(2k) = (a^k)²

可以发现，我们可以通过不断地平方，非常快地得到 a¹, a², a⁴, a⁸... 这一系列“2的幂”次方的项。

迭代实现

这种方法通常比递归实现更好，因为它避免了函数调用开销和潜在的栈溢出风险。

#include <iostream>

/**
 * @brief 计算 (base^exp) % mod 的值
 * * @param base  底数
 * @param exp   指数
 * @param mod   模数
 * @return long long  计算结果
 */
long long power(long long base, long long exp, long long mod) {
    long long res = 1;
    base %= mod; // 预处理，防止 base 过大

    while (exp > 0) {
        // 如果 exp 是奇数, (exp & 1) 的结果为 1
        if (exp & 1) {
            res = (res * base) % mod;
        }
        
        // 将 base 平方
        base = (base * base) % mod;
        
        // 将 exp 右移一位 (相当于除以 2)
        exp >>= 1;
    }
    return res;
}

int main() {
    // 示例：计算 3^5 mod 7
    long long base = 3;
    long long exp = 5;
    long long mod = 7;
    long long result = power(base, exp, mod);
    std::cout << base << "^" << exp << " mod " << mod << " = " << result << std::endl; // 输出: 3^5 mod 7 = 5

    // 示例：计算一个大数的幂
    base = 1234567;
    exp = 87654321;
    mod = 1000000007; // 10^9 + 7
    result = power(base, exp, mod);
    std::cout << "一个大数幂取模的结果: " << result << std::endl;

    return 0;
}

递归实现

虽然不常用，但递归的写法可以帮助理解算法思想。

#include <iostream>

long long power_recursive(long long base, long long exp, long long mod) {
    // 基本情况：任何数的 0 次幂都是 1
    if (exp == 0) {
        return 1;
    }
    
    // 递归计算 (base^(exp/2)) % mod
    long long half = power_recursive(base, exp / 2, mod);
    
    // 将 half 平方
    long long res = (half * half) % mod;
    
    // 如果指数是奇数，需要额外再乘一次 base
    if (exp % 2 == 1) {
        res = (res * base) % mod;
    }
    
    return res;
}

int main() {
    long long result = power_recursive(3, 5, 7);
    std::cout << "递归结果: " << result << std::endl; // 输出: 递归结果: 5
    return 0;
}

具体代码

不使用前缀和，直接硬算指数是可以的

class Solution {
public:
    vector<int> productQueries(int n, vector<vector<int>>& queries) {

        // 直接返回power数组的右上角标即可
        vector<int> exp;
        int i = 0;
        while(n > 0)
        {
            if(n & 1)
            {
                exp.push_back(i);
            }
            n = n >> 1;
            i++;
        }

        // 可以不用前缀和，直接快速幂
        vector<int> result;
        for (const auto& query : queries) {
            int left = query[0];
            int right = query[1];
            long long product = 1;
            long long mod = 1000000007;

            // 直接、清晰的 for 循环
            for (int j = left; j <= right; ++j) {
                // 1. 获取当前位置的指数
                int current_exponent = exp[j];
                
                // 2. 计算 2 的该指数次方 (使用位移最高效)
                long long current_power = 1LL << current_exponent;

                // 3. 将其乘入最终结果，并取模
                product = (product * current_power) % mod;
            }
            
            result.push_back(product);
        }
        
        return result;
    }
};

前缀和方法

class Solution {
private:
    // 辅助函数：快速幂，用于计算 (base^exp) % mod
    long long power(long long base, long long exp) {
        long long res = 1;
        long long mod = 1000000007;
        base %= mod;
        while (exp > 0) {
            if (exp % 2 == 1) {
                res = (res * base) % mod;
            }
            base = (base * base) % mod;
            exp /= 2;
        }
        return res;
    }

public:
    vector<int> productQueries(int n, vector<vector<int>>& queries) {
        
        // 步骤一：找出 n 的二进制表示中所有为'1'的位的索引
        vector<int> exponents;
        for (int i = 0; i < 31; ++i) {
            if ((n >> i) & 1) {
                exponents.push_back(i);
            }
        }

        // 步骤二：创建指数数组的前缀和数组
        vector<long long> prefix_sum_of_exponents(exponents.size() + 1, 0);
        for (int i = 0; i < exponents.size(); ++i) {
            prefix_sum_of_exponents[i + 1] = prefix_sum_of_exponents[i] + exponents[i];
        }

        // 步骤三：遍历所有查询
        vector<int> answers;
        for (const auto& query : queries) {
            int left = query[0];
            int right = query[1];

            // 步骤 3.1: 使用前缀和数组计算区间指数总和
            long long total_exponent = prefix_sum_of_exponents[right + 1] - prefix_sum_of_exponents[left];
            
            // 步骤 3.2: 使用快速幂计算结果
            long long result = power(2, total_exponent);
            
            answers.push_back(static_cast<int>(result));
        }
        
        return answers;
    }
};

进一步优化思路

查表：预计算2的幂

观察查询循环中的关键部分：

// ...
total_exponent = prefix_sum_of_exponents[right + 1] - prefix_sum_of_exponents[left];
result = power(2, total_exponent); // 每次查询都调用一次快速幂

这里的瓶颈在于，尽管快速幂很快（O(log(exponent))），但我们仍然为 Q 次查询调用了 Q 次 power 函数。

优化的关键在于：我们注意到，power 函数的底数始终是 2。这意味着我们求的永远是 2 的某个次方。既然如此，我们完全可以提前把所有可能用到的 2 的幂次计算出来，存到一个查找表（数组或 vector）里。

之后，每次查询我们只需要计算出总指数 total_exponent，然后直接去表里查结果，把 O(log(exponent)) 的函数调用变成 O(1) 的数组访问。

优化步骤

1. 确定最大指数：exponents 数组最多包含约 30 个从 0 到 29 的数。所有指数的和最大为 0 + 1 + 2 + ... + 29，这个和是 (29 * 30) / 2 = 435。所以我们的指数不会超过 450。(在实际上，我们可以不断缩小这个数找到测试集的边界值，因为在指数很大的时候，这个计算是时间复杂度的主要性能，并且指数越大计算时间越长，那么减少这个指数值就可以尽快的加速。)
2. 创建查找表：创建一个大小约为 450 的数组 powers_of_2。
   • powers_of_2[i] 将存储 (2^i) % mod 的值。
3. 预计算填充表格：
   • powers_of_2[0] = 1;
   • powers_of_2[i] = (powers_of_2[i-1] * 2) % mod;
4. 修改查询逻辑：
   • 计算出 total_exponent 后，不再调用 power(2, total_exponent)。
   • 直接通过 answers.push_back(powers_of_2[total_exponent]); 来获取结果。

优化后代码

#include <vector>

// 引入标准命名空间，简化代码书写
using namespace std;

class Solution {
public:
    vector<int> productQueries(int n, vector<vector<int>>& queries) {
        
        // 定义模数，用于防止计算结果溢出。题目要求为 10^9 + 7。
        // 使用 long long 类型以确保中间乘法过程不会溢出。
        long long mod = 1000000007;

        // ========================================================================
        // 步骤一：构建指数数组 (exponents)
        // 目标：将 n 分解为其二进制表示中 2 的幂的和，并记录这些幂的指数。
        // 例如：n=15 (二进制 1111) -> powers=[2^0, 2^1, 2^2, 2^3] -> exponents=[0, 1, 2, 3]
        // ========================================================================
        vector<int> exponents;
        // 题目约束 n <= 10^9，而 2^30 > 10^9，所以我们只需要检查 0 到 30 位即可。
        for (int i = 0; i < 31; ++i) {
            // (n >> i) & 1 是一个位运算技巧，用于检查 n 的二进制表示中从右数的第 i 位是否为 1。
            if ((n >> i) & 1) {
                // 如果第 i 位是 1，说明 2^i 是构成 n 的一部分，将其指数 i 存入数组。
                exponents.push_back(i);
            }
        }

        // ========================================================================
        // 步骤二：构建指数的前缀和数组 (prefix_sum_of_exponents)
        // 目标：预计算指数的和，使得后续可以 O(1) 时间复杂度查询任意区间的指数之和。
        // 这是解决“多次区间查询”问题的经典高效模式。
        // ========================================================================
        // 数组长度比 exponents 多 1，是为了方便计算。prefix_sum[i] 存储 exponents[0]...exponents[i-1] 的和。
        vector<long long> prefix_sum_of_exponents(exponents.size() + 1, 0);
        for (int i = 0; i < exponents.size(); ++i) {
            // 递推关系：当前位置的前缀和 = 前一个位置的前缀和 + 当前元素值。
            prefix_sum_of_exponents[i + 1] = prefix_sum_of_exponents[i] + exponents[i];
        }

        // ========================================================================
        // 步骤三：预计算所有可能用到的 2 的幂 (powers_of_2 查找表)
        // 目标：将后续需要多次进行的快速幂运算，优化为 O(1) 的查表操作。
        // 这是本题最终性能优化的关键，用空间换时间。
        // ========================================================================
        // 我们需要确定最大可能的指数和。指数最大为 29，最多有 30 个。
        // 最大和为 0+1+...+29 = 435。所以表格大小设为 450+1=451 是非常安全的。
        vector<long long> powers_of_2(451);
        // 任何数的 0 次方都是 1。
        powers_of_2[0] = 1;
        for (int i = 1; i <= 450; ++i) {
            // 2^i = (2^(i-1)) * 2。通过前一项可以 O(1) 推算出后一项。
            powers_of_2[i] = (powers_of_2[i - 1] * 2) % mod;
        }

        // ========================================================================
        // 步骤四：遍历所有查询，计算并存储结果
        // ========================================================================
        vector<int> answers;
        // 预留空间，避免 vector 在 push_back 时可能发生的耗时内存重分配。
        answers.reserve(queries.size()); 
        
        // 使用 C++11 的范围 for 循环，简洁且安全地遍历所有查询。
        for (const auto& query : queries) {
            int left = query[0];
            int right = query[1];

            // 核心步骤 4.1: 利用前缀和数组，在 O(1) 时间内计算出 [left, right] 区间的指数总和。
            // sum(left..right) = sum(0..right) - sum(0..left-1)
            long long total_exponent = prefix_sum_of_exponents[right + 1] - prefix_sum_of_exponents[left];
            
            // 核心步骤 4.2: 直接从预计算的查找表中 O(1) 获取 2^total_exponent 的结果。
            // 这里取代了原先需要 O(log(exponent)) 时间的快速幂函数调用。
            answers.push_back(powers_of_2[total_exponent]);
        }
        
        // 返回最终的答案数组
        return answers;
    }
};