Static Range Query (ds/srq.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2025-09-18 22:02:23+07:00
• Include: #include "ds/srq.hpp"
• Link: https://usaco.guide/plat/DC-SRQ

Description

Static Range Query (SRQ) solves offline range queries using divide and conquer. For each query [l, r), it computes op(v[l], v[l+1], ..., v[r-1]) where op is an associative operation.

Operations

• RangeQuery<T, Q, Op>(const vector<T> &v, const vector<Q> &q, Op op, T e)
  • Constructs SRQ instance with array v, queries q, operation op, and identity e
  • Each query Q must have fields l and r representing range [l, r)
  • Time complexity: $\mathcal O(n + q)$
• void solve()
  • Solves all queries and stores results in ans vector
  • Time complexity: $\mathcal O((n + q) \log n)$
• make_rq(const vector<T> &v, const vector<Q> &q, Op op, T e)
  • Helper function to create a RangeQuery instance
  • Time complexity: $\mathcal O(n + q)$

Code

#pragma once

// https://usaco.guide/plat/DC-SRQ
// Not really optimized I just wrote this on a whim
template<class T, class Q, class Op> struct RangeQuery {
    RangeQuery(const vector<T> &v, const vector<Q> &_q, Op _op, T e) :
        ans((int)_q.size()), n((int)v.size()), d(v), lef(n, e), rig(n, e),
        idx((int)_q.size()), q(_q), op(_op) {
        iota(begin(idx), end(idx), 0);
    }
    void solve() { _solve(0, n - 1, idx); }

    vector<T> ans;

  private:
    int n;
    vector<T> d, lef, rig;
    vector<int> idx;
    vector<Q> q;
    Op op;
    void _solve(int l, int r, vector<int> &qry) {
        if (qry.empty()) return;
        if (l == r) {
            for (int &i : qry) ans[i] = d[l];
            return;
        }
        int m = (l + r) / 2;
        lef[m] = d[m];
        for (int i = m - 1; i >= l; i--) lef[i] = op(d[i], lef[i + 1]);
        rig[m + 1] = d[m + 1];
        for (int i = m + 2; i < r + 1; i++) rig[i] = op(rig[i - 1], d[i]);
        vector<int> le, ri;
        for (int i : qry) {
            if (q[i].l <= m && m < q[i].r) {
                ans[i] = op(lef[q[i].l], rig[q[i].r]);
                continue;
            }
            (q[i].l <= m ? le : ri).push_back(i);
        }
        _solve(l, m, le);
        _solve(m + 1, r, ri);
    }
};
template<class T, class Q, class Op>
auto make_rq(const vector<T> &v, const vector<Q> &q, Op op, T e) {
    return RangeQuery<T, Q, Op>{v, q, op, e};
}

#line 2 "ds/srq.hpp"

// https://usaco.guide/plat/DC-SRQ
// Not really optimized I just wrote this on a whim
template<class T, class Q, class Op> struct RangeQuery {
    RangeQuery(const vector<T> &v, const vector<Q> &_q, Op _op, T e) :
        ans((int)_q.size()), n((int)v.size()), d(v), lef(n, e), rig(n, e),
        idx((int)_q.size()), q(_q), op(_op) {
        iota(begin(idx), end(idx), 0);
    }
    void solve() { _solve(0, n - 1, idx); }

    vector<T> ans;

  private:
    int n;
    vector<T> d, lef, rig;
    vector<int> idx;
    vector<Q> q;
    Op op;
    void _solve(int l, int r, vector<int> &qry) {
        if (qry.empty()) return;
        if (l == r) {
            for (int &i : qry) ans[i] = d[l];
            return;
        }
        int m = (l + r) / 2;
        lef[m] = d[m];
        for (int i = m - 1; i >= l; i--) lef[i] = op(d[i], lef[i + 1]);
        rig[m + 1] = d[m + 1];
        for (int i = m + 2; i < r + 1; i++) rig[i] = op(rig[i - 1], d[i]);
        vector<int> le, ri;
        for (int i : qry) {
            if (q[i].l <= m && m < q[i].r) {
                ans[i] = op(lef[q[i].l], rig[q[i].r]);
                continue;
            }
            (q[i].l <= m ? le : ri).push_back(i);
        }
        _solve(l, m, le);
        _solve(m + 1, r, ri);
    }
};
template<class T, class Q, class Op>
auto make_rq(const vector<T> &v, const vector<Q> &q, Op op, T e) {
    return RangeQuery<T, Q, Op>{v, q, op, e};
}

Back to top page