linear cum sum

ソースコード

 1#include <vector>
 2#include <cassert>
 3using namespace std;
 4
 5namespace titan23 {
 6
 7template<typename T>
 8class LinearCumSum {
 9private:
10    int n;
11    int B; // バケットサイズ
12    vector<T> A;
13    vector<vector<vector<T>>> S, Si;
14
15    void build() {
16        S.resize(B+1);
17        Si.resize(B+1);
18        for (int d = 1; d < B; ++d) {
19            S[d].resize(d+1);
20            Si[d].resize(d+1);
21            for (int k = 0; k < d; ++k) {
22                S[d][k].resize(n/d+2);
23                Si[d][k].resize(n/d+2);
24            }
25            for (int i = 0; i < n; ++i) {
26                S[d][i%d][i/d+1] = S[d][i%d][i/d] + A[i];
27                Si[d][i%d][i/d+1] = Si[d][i%d][i/d] + A[i]*(i/d+1);
28            }
29        }
30    }
31
32public:
33    LinearCumSum() {}
34
35    LinearCumSum(const vector<T> &a) {
36        n = (int)a.size();
37        B = (int)sqrt(n);
38        A = a;
39        build();
40    }
41
42    // a_l * 1 + a_{l+d} * 2 + ... + a_{l+(k-1)*d} * k
43    T sum(int l, int d, int k, ll a, ll b) {
44        // https://codeforces.com/contest/1921/problem/F
45        assert(l+d*(k-1) < n);
46        assert(a == 1);
47        if (d >= B) { // naive
48            T s = 0;
49            int idx = 1;
50            for (int i = l; i <= l+d*(k-1); i += d) {
51                s += A[i] * idx;
52                idx++;
53            }
54            return s;
55        } else {
56            int end = l+d*(k-1);
57            T s = Si[d][l%d][end/d+1] - Si[d][l%d][l/d];
58            s -= (S[d][l%d][end/d+1] - S[d][l%d][l/d]) * (l/d);
59            return s;
60        }
61    }
62};
63} // namespace titan23

仕様

Warning

doxygenfile: Cannot find file “titan_cpplib/data_structures/linear_cum_sum.cpp