Divide & Conquer - SRQ

Static Array Queries

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

where $\ominus$ denotes an associative operation.

In the prerequisite 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=\lfloor \frac{L+R}{2}\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

1int n,q,A[MX],B[MX];
2vi x, ans;
3int lef[MX], rig[MX];
4
5void divi(int l, int r, vi v) {
6    if (!sz(v)) return;
7    if (l == r) {
8        trav(_,v) ans[_] = x[l];
9        return;
10    }

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 training 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 training zeroes in mask[12] XOR mask[18], which is 1. So our answer is min(dat[1][12],dat[1][12]).

1int n,q;
2vi x, ans;
3 
4int dat[18][MX], mask[MX]; // 18 = ceil(log2(n))
5 
6void divi(int l, int r, int lev) { // generate dat and mask
7    if (l == r) return;
8    int m = (l+r)/2; 
9    dat[lev][m] = x[m]; 
10    ROF(i,l,m) dat[lev][i] = min(x[i],dat[lev][i+1]);

Problems