Disjoint Sparse Table
For an associative operation , a range query asks for
2D Sparse Table for Rectangle Minimum Queries
An ordinary sparse table answers a general associative query in by combining disjoint blocks. Its query uses overlapping segments and requires that repeating elements does not change the result.
A disjoint sparse table combines two segments without overlap. It therefore works with any associative operation. Commutativity is not required: the elements are combined in their original order.
Indices start at , and query intervals are inclusive.
At level , divide the array into blocks of length , starting from position . A block starting at has midpoint
For each position in the left half, store the suffix ending at :
For each position in the right half, store the prefix starting at :
Build the suffixes from right to left, adding each new element on the left. Build the prefixes from left to right, adding each new element on the right. This preserves the order of the operation.
The last block may be shorter. Process only existing positions, and skip a block if its right half is empty.
If , return .
Otherwise, let be the position of the highest set bit in :
Here is bitwise XOR.
All bits above are equal, so and belong to the same block of length . Their bit differs. Since , that bit is in and in , placing them in the left and right halves.
At this level, covers , and covers . These two segments are disjoint and cover the query exactly. The answer is
Combine the left suffix first, then the right prefix.
Each level processes entries, and there are levels. Preprocessing takes time, and each query takes time.
The table uses entries; the global arrays reserve space for the maximum supported size. These bounds assume each stored value uses space and combining two values takes time.
The array stays fixed after preprocessing.
#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
const int K = 20;
const int MOD = 1000;
int n;
long long a[N], t[K][N];
long long op(long long x, long long y) {
return x * y % MOD;
}
void build() {
for (int k = 0; (1 << k) < n; k++) {
int b = 1 << k;
for (int l = 0; l < n; l += 2 * b) {
int m = min(l + b, n);
int r = min(l + 2 * b, n);
if (m == r) continue;
t[k][m - 1] = a[m - 1];
for (int i = m - 2; i >= l; i--) {
t[k][i] = op(a[i], t[k][i + 1]);
}
t[k][m] = a[m];
for (int i = m + 1; i < r; i++) {
t[k][i] = op(t[k][i - 1], a[i]);
}
}
}
}
long long get(int l, int r) {
if (l == r) return a[l];
int k = 31 - __builtin_clz((unsigned int)(l ^ r));
return op(t[k][l], t[k][r]);
}