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 , you want to answer queries in the form

where denotes an associative operation.

In the prerequisite module, it was shown that we can get time queries with time preprocessing when denotes min. But how do we generalize to other associative operations?

We can use divide & conquer to answer queries offline in time or online in .

Offline Queries

Suppose that all queries satisfy (initially, and ). Letting , we can compute

for all and

for each . Then the answer for all queries satisfying is simply due to the associativity condition. After that, we recurse on all query intervals completely contained within and 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

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 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 . For example, if and we only consider levels and 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]).
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]);
Optional: Faster Preprocessing

A data structure known as sqrt-tree can speed up preprocessing time and memory to .

Problems

StatusSourceProblem NameDifficultyTagsSolutionURL
JOIEasy
CCEasyCheck CC
Baltic OINormal
DMOJNormalCheck DMOJ
PlatHardExternal Sol

Module Progress:

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

Give Us Feedback on Divide & Conquer - SRQ!

Leave suggestions for us by making a post on the USACO Forum! Ex: Unclear sections, mislabeled problems, etc.

PrevNext