Offline Queries
Reorder queries so that one sweep or one monotone data-structure state can answer them more cheaply than online processing.
Offline Queries
The main note is rendered from the TeX source. Code lives in a separate C++ file so the write-up stays readable.
Overview
Offline queries are the answer when online order is a burden rather than a requirement. If all queries are known in advance, I can sort or bucket them into a friendlier order and maintain a data structure state that only moves forward.
When to Use It
Use offline processing when:
all queries are available before answering begins,
sorting queries by one parameter makes updates monotone,
the online version would require a more complex data structure.
Core Idea
Choose an order in which processing becomes incremental. A common example is:
sort array elements by value,
sort range queries by threshold \(x\),
add all elements with value \(\le x\) to a Fenwick tree before answering that query.
Key Insight
Offline means I am allowed to change time order as long as I remember the original query indices. That freedom often replaces a hard dynamic problem with a simple sweep.
Operations / Main Technique
annotate each query with its original index,
sort by a parameter that should move monotonically,
sweep through updates and answer queries in that order,
restore the original answer order at the end.
Worked example.
To count how many values in \([l, r]\) are at most \(x\), sort the queries by \(x\), insert positions of array values in increasing-value order into a Fenwick tree, and query the active-count range when each threshold is reached.
Correctness Intuition
The sorted sweep ensures that, before answering a query with threshold \(x\), the data structure exactly represents all contributions that should be active for that threshold and none that should not. The original query order is irrelevant once the answers are stored by index.
Complexity Analysis
Typical offline sweeps cost \(O((n + q)\log n)\) after sorting, instead of paying for a heavier online structure.
Implementation
The sample code implements the threshold-query pattern described above with a Fenwick tree. It answers range counts of values \(\le x\).
Common Pitfalls
Forgetting to preserve original query indices.
Sorting by the wrong key so the sweep state no longer matches the query meaning.
Forcing an offline solution when the statement requires interactive or online answers.
Variants / Extensions
Mo's algorithm for reordering by block locality.
Parallel binary search.
CDQ divide and conquer for time-ordered offline events.
Practice Problems
Count values \(\le x\) in subarrays.
Offline rectangle counting after coordinate compression.
Process add-and-query events after sorting by time or threshold.
References
cp-algorithms: Fenwick Tree for the standard sweep helper.
Code
Contest-ready reference implementation for the idea explained above.
struct Fenwick {
int n;
vector<int> bit;
explicit Fenwick(int n) : n(n), bit(n + 1, 0) {}
void add(int idx, int delta) {
for (++idx; idx <= n; idx += idx & -idx) {
bit[idx] += delta;
}
}
int sum_prefix(int idx) const {
int result = 0;
for (++idx; idx > 0; idx -= idx & -idx) {
result += bit[idx];
}
return result;
}
int sum_range(int l, int r) const {
return sum_prefix(r) - (l ? sum_prefix(l - 1) : 0);
}
};
struct ThresholdQuery {
int l;
int r;
int x;
int id;
};
vector<int> count_values_at_most(const vector<int>& a, vector<ThresholdQuery> queries) {
vector<pair<int, int>> values;
for (int i = 0; i < (int)a.size(); ++i) {
values.push_back({a[i], i});
}
sort(values.begin(), values.end());
sort(queries.begin(), queries.end(), [](const ThresholdQuery& lhs, const ThresholdQuery& rhs) {
return lhs.x < rhs.x;
});
Fenwick fw((int)a.size());
vector<int> answer(queries.size(), 0);
int ptr = 0;
for (const ThresholdQuery& q : queries) {
while (ptr < (int)values.size() && values[ptr].first <= q.x) {
fw.add(values[ptr].second, 1);
++ptr;
}
answer[q.id] = fw.sum_range(q.l, q.r);
}
return answer;
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.