无限数组区间和查询问题及非最优解法的优化咨询

给定整数数组A，定义无限数组B为A的无限次拼接（例如A=[1,2,3]时，B为[1,2,3,1,2,3,...]）。给定q次查询，每次查询包含1-based索引的L和R，需计算B中从L到R（两端均包含）的子数组和，结果需对10^9+7取模。

输入格式 #

• 第一行输入整数T表示测试用例数；
• 每个测试用例：
  • 第一行输入整数N表示数组A的大小；
  • 第二行输入N个空格分隔的整数作为A的元素；
  • 第三行输入整数Q表示查询数；
  • 后续Q行每行输入两个空格分隔的整数L和R。

我自己实现了一个双指针解法，但觉得这个解法效率太低，想找更优的方案，以下是我的代码：

#include <iostream>
#include <vector>
vector<int> sumInRanges(vector<int> &arr, int n, vector<vector<long long>> &queries, int q) {
    // Write your code here
    vector<int> res;
    
    for(int i = 0; i < q; i++){
        int sum = 0;
        int start = queries[i][0];
        int end = queries[i][1];
        while( start <= end ){
            if(start < arr.size()){
                sum += arr[start - 1];
            }
            else{
                int mod = start % arr.size();
                sum += arr[mod - 1];
            }
        }
        res.push_back(sum);
    }
    
    return res;
}

你当前的解法存在几个关键问题：一是时间复杂度爆炸，如果查询的区间长度达到1e18，循环会直接超时；二是代码本身有bug（比如没写start++导致死循环、用int存超大的L/R会溢出、没按要求对结果取模）。

最优解法是利用前缀和数组+数学规律直接计算，完全避免遍历区间内的每个元素，步骤如下：

步骤1：预处理前缀和与数组总和 #

• 计算数组A的总和total_sum，全程对1e9+7取模；
• 构建前缀和数组prefix，其中prefix[i]表示A的前i个元素的和（prefix[0]=0，prefix[1]=A[0]，prefix[2]=A[0]+A[1]，以此类推），同样对1e9+7取模。

步骤2：单个查询的计算逻辑 #

对于每个查询的L和R，我们可以把区间和拆成「前R项的和」减去「前L-1项的和」，再取模处理负数：

1. 计算前X项的和sum_X：
   • 完整的A数组重复次数：full_cycles = X / n；
   • 剩余的元素个数：remainder = X % n；
   • sum_X = (full_cycles * total_sum % MOD + prefix[remainder]) % MOD；
2. 区间[L,R]的和 = (sum_R - sum_L-1 + MOD) % MOD，加MOD是为了避免减法出现负数。

完整优化代码 #

#include <iostream>
#include <vector>
using namespace std;

const int MOD = 1e9 + 7;

vector<int> sumInRanges(vector<int> &arr, int n, vector<vector<long long>> &queries, int q) {
    vector<long long> prefix(n + 1, 0);
    long long total_sum = 0;
    
    // 预处理前缀和与数组总和
    for (int i = 0; i < n; ++i) {
        total_sum = (total_sum + arr[i]) % MOD;
        prefix[i + 1] = (prefix[i] + arr[i]) % MOD;
    }
    
    vector<int> res;
    for (auto &query : queries) {
        long long L = query[0];
        long long R = query[1];
        
        // 计算前R项的和
        long long full_R = R / n;
        long long rem_R = R % n;
        long long sum_R = (full_R % MOD) * total_sum % MOD;
        sum_R = (sum_R + prefix[rem_R]) % MOD;
        
        // 计算前L-1项的和
        long long L_1 = L - 1;
        long long full_L = L_1 / n;
        long long rem_L = L_1 % n;
        long long sum_L = (full_L % MOD) * total_sum % MOD;
        sum_L = (sum_L + prefix[rem_L]) % MOD;
        
        // 计算区间和，处理负数情况
        long long ans = (sum_R - sum_L + MOD) % MOD;
        res.push_back((int)ans);
    }
    
    return res;
}

优化后的优势 #

• 时间复杂度：预处理是O(n)，每个查询是O(1)，总复杂度为O(T*(n+q))，完全能处理超大范围的L/R（比如1e18）；
• 彻底避免了遍历区间元素，不会因为区间过大超时；
• 用long long存储中间结果，避免数值溢出，且严格按照要求对每一步取模。

内容的提问来源于stack exchange，提问作者Pinak faldu