前缀和问题｜离线算法&分块

T5 - 前缀和问题

题目链接跳转：点击跳转

我个人认为这道题比最后一道题要难，也许是因为这类题目做的比较少的原因，看到题目后不知道从哪下手。

使用分类讨论的方法，设置一个阈值 $S$，考虑暴力枚举所有 $b > S$ 的情况，并离线优化 $b \le S$ 的情况。将 $S$ 设置为 $\sqrt{N}$，则有：

1. 对于大步长 $b > S$，任意一次查询只需要最多遍历 $550$（即 $\sqrt{N}$）次就可以算出答案，因此暴力枚举这部分。
2. 对于小步长 $b \le S$，按 $b$ 分组批量离线查询。

对于大步长部分，每一次查询的时间复杂度为 $O(\sqrt{N})$，在最坏情况下总时间复杂度为 $O(N \times \sqrt{N})$。对于小步长的部分，每一次查询的时间复杂度约为 $O(n)$，在最坏情况下的时间复杂度为 $O(N\times \sqrt{N})$，因此本题在最坏情况下的渐进时间复杂度为：

$$\large{O(N \times \sqrt{N})}$$

最后，本题的 C++ 代码如下：

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

struct Query {
    int id;  
    int a, b;   
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    int n; cin >> n;
    
    vector<LL> a_arr(n + 1, 0);
    for(int i =1; i <=n; i++) cin >> a_arr[i];
    
    int q; cin >> q;
    
    vector<Query> queries(q);
    for(int i =0; i < q; i++){
        cin >> queries[i].a >> queries[i].b;
        queries[i].id = i;
    }
    
    int S = 550;
    
    // 分组查询：小步长和大步长
    // 对于小步长 b <= S，按 b 分组
    // 对于大步长 b > S，单独存储
    vector<vector<pair<int, int>>> small_b_queries(S +1, vector<pair<int, int>>()); // small_b_queries[b]存储 (a, id)
    vector<pair<int, int>> large_b_queries; // 存储 (a, id) for b > S
    
    for(int i =0; i < q; i++) {
        if(queries[i].b <= S)
            small_b_queries[queries[i].b].emplace_back(queries[i].a, queries[i].id);
        else
            large_b_queries.emplace_back(make_pair(queries[i].a, queries[i].id));
    }
    
    vector<LL> res(q, 0);
    
    // 预处理小步长查询
    // 对每个 b =1 to S
    for(int b =1; b <= S; b++){
        if(small_b_queries[b].empty()) continue;
        
        // 创建一个临时数组 s_arr，用于存储当前步长 b 的累加和
        // 从 n downto 1
        // s_arr[a] = a_arr[a] + s_arr[a + b] (如果 a + b <=n)
        // 否则 s_arr[a] = a[a]
        vector<LL> s_arr(n + 5, 0);
        for(int a = n; a >=1; a--){
            if(a + b <= n){
                s_arr[a] = a_arr[a] + s_arr[a + b];
            }
            else{
                s_arr[a] = a_arr[a];
            }
        }
        
        // 回答所有步长为 b 的查询
        for(auto &[a, id] : small_b_queries[b]){
            res[id] = s_arr[a];
        }
    }
    
    // 处理大步长查询
    // 由于 b > S，且 S = 550，所以每个查询最多需要 ~550 次操作
    for(auto &[a, id] : large_b_queries){
        LL sum = 0;
        int current = a;
        while(current <= n){
            sum += a_arr[current];
            current += queries[id].b;
        }
        res[id] = sum;
    }
    
    for(int i =0; i < q; i++) 
        cout << res[i] << "\n";
    
    return 0;
}

本题的 Python 代码如下（不保证可以通过所有的测试点）：

class Query:
    def __init__(self, id, a, b):
        self.id = id
        self.a = a
        self.b = b

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    n = int(data[0])
    a_arr = [0] * (n + 1)
    for i in range(1, n + 1):
        a_arr[i] = int(data[i])
    
    q = int(data[n + 1])
    queries = []
    idx = n + 2
    for i in range(q):
        a, b = int(data[idx]), int(data[idx + 1])
        queries.append(Query(i, a, b))
        idx += 2
    
    S = 550
    small_b_queries = [[] for _ in range(S + 1)]
    large_b_queries = []
    
    for query in queries:
        if query.b <= S:
            small_b_queries[query.b].append((query.a, query.id))
        else:
            large_b_queries.append((query.a, query.id))
    
    res = [0] * q
    
    for b in range(1, S + 1):
        if not small_b_queries[b]:
            continue
        
        s_arr = [0] * (n + 5)
        for a in range(n, 0, -1):
            if a + b <= n:
                s_arr[a] = a_arr[a] + s_arr[a + b]
            else:
                s_arr[a] = a_arr[a]
        
        for a, id in small_b_queries[b]:
            res[id] = s_arr[a]
    
    for a, id in large_b_queries:
        sum_val = 0
        current = a
        b = queries[id].b
        while current <= n:
            sum_val += a_arr[current]
            current += b
        res[id] = sum_val
    
    sys.stdout.write("\n".join(map(str, res)) + "\n")

if __name__ == "__main__":
    main()