PrevNext
Rare
 0/6

Divide & Conquer - SRQ

Authors: Benjamin Qi, Andi Qu

Using Divide & Conquer to answer offline or online range queries on a static array.

Static Array Queries

Focus Problem – read through this problem before continuing!

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

A[l]A[l+1]A[r]A[l]\ominus A[l+1]\ominus \cdots \ominus A[r]

where \ominus denotes an associative operation.

In the prerequisite module, it was shown that we can get O(1)O(1) time queries with O(NlogN)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 QQ queries offline in O((N+Q)logN)O((N+Q)\log N) time or online in O(NlogN+Q)O(N\log N+Q).

Offline Queries

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

lef[l]=A[l]A[l+1]A[M]lef[l]=A[l]\ominus A[l+1]\ominus \cdots \ominus A[M]

for all LlML\le l\le M and

rig[r]=A[M+1]A[M+2]A[r]rig[r]=A[M+1]\ominus A[M+2] \ominus \cdots\ominus A[r]

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

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

Warning!

Be careful to combine elements in the appropriate order if the operation is not commutative.

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 O(NlogN)O(N\log N) memory, similarly as sparse table.

Resources
Benqimplementation

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]A[l+1]A[r]A[l]\ominus A[l+1]\ominus \cdots \ominus A[r]. For example, if n=20n=20 and we only consider levels 00 and 11 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]);
Optional: Faster Preprocessing

A data structure known as sqrt-tree can speed up preprocessing time and memory to O(NloglogN)O(N\log \log N).

Problems

StatusSourceProblem NameDifficultyTagsSolution
JOIEasy
CCEasyCheck CC
Baltic OINormal
DMOJNormalCheck DMOJ
PlatHardExternal Sol

Module Progress:

Give Us Feedback on Divide & Conquer - SRQ!

PrevNext