Divide & Conquer - SRQ

Static Array Queries

Given a static array $A[1],A[2],\ldots,A[N]$, you want to answer queries in the form

where $\ominus$ denotes an associative operation.

In a previous module, it was shown that we can get $\mathcal{O}(1)$ time queries with $\mathcal{O}(N\log N)$ time preprocessing when $\ominus$ denotes min. But how do we generalize to other associative operations?

We can use divide & conquer to answer $Q$ queries offline in $\mathcal{O}((N+Q)\log N)$ time or online in $\mathcal{O}(N\log N+Q)$.

Offline Queries

Suppose that all queries satisfy $L\le l\le r\le R$ (initially, $L=1$ and $R=N$). Letting $M=\left\lfloor \frac{L+R}{2}\right\rfloor$, we can compute

for all $L\le l\le M$ and

for each $M< r\le R$. Then the answer for all queries satisfying $l\le M< r$ is simply $lef[l]\ominus rig[r]$ due to the associativity condition. After that, we recurse on all query intervals completely contained within $[L,M]$ and $[M+1,R]$ independently.

The code below should work if min is replaced by any associative operation.

Solution - RMQ

Copy
int n, q, A[MX], B[MX];
vi x, ans;
int lef[MX], rig[MX];

void divi(int l, int r, vi v) {
	if (!sz(v)) return;
	if (l == r) {
		trav(_, v) ans[_] = x[l];
		return;
	}

Online Queries

We do the same thing as above, except we store all computes values of lef and rig within a 2D array using $\mathcal{O}(N\log N)$ memory, similarly as sparse table.

Solution - RMQ

In the code below, dat performs the roles that both lef and rig do in the previous solution. Let comb(l,r) equal $A[l]\ominus A[l+1]\ominus \cdots \ominus A[r]$. For example, if $n=20$ and we only consider levels $0$ and $1$ then we get

• dat[0][i]=comb(i,9) for i in [0,9]
• dat[0][i]=comb(10,i) for i in [10,19]
• dat[1][i]=comb(i,4) for i in [0,4]
• dat[1][i]=comb(5,i) for i in [5,9]
• dat[1][i]=comb(i,14) for i in [10,14]
• dat[1][i]=comb(15,i) for i in [15,19]
• mask[0..4]=0
• mask[5..9]=2
• mask[10..14]=1
• mask[15..19]=3

Examples of queries:

• To query comb(0,16) we first count the number of trailing zeroes in mask[0] XOR mask[16], which is 0. So our answer is min(dat[0][0],dat[0][16]).
• To query comb(12,18) we first count the number of trailing zeroes in mask[12] XOR mask[18], which is 1. So our answer is min(dat[1][12],dat[1][18]).

Copy
int n, q;
vi x, ans;

int dat[18][MX], mask[MX];  // 18 = ceil(log2(n))

void divi(int l, int r, int lev) {  // generate dat and mask
	if (l == r) return;
	int m = (l + r) / 2;
	dat[lev][m] = x[m];
	ROF(i, l, m) dat[lev][i] = min(x[i], dat[lev][i + 1]);

Problems