verifying_test/yosupo/data_structure/static_range_sum/disjoint_sparse_table.test.cpp

View this file on GitHub
Last update: 2022-01-28 02:17:51+09:00
Problem: https://judge.yosupo.jp/problem/static_range_sum

Depends on

Disjoint Sparse Table (structure/disjoint_sparse_table.cpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/static_range_sum"

#include <vector>
#include <cstdio>
using namespace std;
using ll = long long int;

#define call_from_test
#include "../../../../structure/disjoint_sparse_table.cpp"
#undef call_from_test

int main() {
    int N, Q; scanf("%d%d", &N, &Q);
    vector<ll> A(N);
    for(int i=0; i<N; i++) scanf("%lld", &A[i]);

    DisjointSparseTable<ll> dst(A, [](ll x, ll y) { return x + y; });
    while(Q--) {
        int l, r; scanf("%d%d", &l, &r);
        printf("%lld\n", dst.query(l, r));
    }
    return 0;
}

#line 1 "verifying_test/yosupo/data_structure/static_range_sum/disjoint_sparse_table.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/static_range_sum"

#include <vector>
#include <cstdio>
using namespace std;
using ll = long long int;

#define call_from_test
#line 2 "structure/disjoint_sparse_table.cpp"

// @brief Disjoint Sparse Table
// @see https://noshi91.hatenablog.com/entry/2018/05/08/183946
// @docs docs/structure/disjoint_sparse_table.md

#line 8 "structure/disjoint_sparse_table.cpp"
#include <functional>
#include <cassert>

template <typename Tp>
struct DisjointSparseTable {
    int N, LN;
    vector<Tp> A;
    vector< vector<Tp> > seg_l, seg_r;
    function<Tp(Tp, Tp)> cmb_f;
    
    DisjointSparseTable() = default;
    DisjointSparseTable(vector<Tp> A_,
                        function<Tp(Tp, Tp)> cmb_f_)
        : A(A_), cmb_f(cmb_f_) {
        N = A.size(), LN = 1;
        while((1<<LN) < N) LN++;
        seg_l.resize(LN, vector<Tp>(N));
        seg_r.resize(LN, vector<Tp>(N));
        build(A);
    }

    void build(const vector<Tp> &A) {
        for(int i=0; i<LN; i++) {
            // [j-(1<<i), j), [ j, j+(1<<i) )
            for(int j=(1<<i); j<=N; j+=(1<<(i+1))) {
                if(j < N) seg_r[i][j] = A[j];
                for(int k=j+1; k<j+(1<<i); k++) {
                    if(k >= N) break;
                    seg_r[i][k] = cmb_f(seg_r[i][k-1], A[k]);
                }
                if(j-1 >= 0) seg_l[i][j-1] = A[j-1];
                for(int k=j-2; k>=j-(1<<i); k--) {
                    if(k < 0) break;
                    seg_l[i][k] = cmb_f(seg_l[i][k+1], A[k]);
                }
            }
        }
    }

    Tp query(int l, int r) {
        assert(0 <= l and l < r and r <= N); r--;
        if(l == r) return A[l];
        int k = 31 - __builtin_clz((unsigned int)(l ^ r));
        return cmb_f(seg_l[k][l], seg_r[k][r]);
    }
};
#line 10 "verifying_test/yosupo/data_structure/static_range_sum/disjoint_sparse_table.test.cpp"
#undef call_from_test

int main() {
    int N, Q; scanf("%d%d", &N, &Q);
    vector<ll> A(N);
    for(int i=0; i<N; i++) scanf("%lld", &A[i]);

    DisjointSparseTable<ll> dst(A, [](ll x, ll y) { return x + y; });
    while(Q--) {
        int l, r; scanf("%d%d", &l, &r);
        printf("%lld\n", dst.query(l, r));
    }
    return 0;
}