PrevNext
Rare
 0/8

Divide & Conquer - SRQ

Authors: Benjamin Qi, Andi Qu

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

Edit This Page

Static Array Queries

Focus Problem – try your best to solve 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 a previous module, it was shown that we can get O(1)\mathcal{O}(1) time queries with O(NlogN)\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 QQ queries offline in O((N+Q)logN)\mathcal{O}((N+Q)\log N) time or online in O(NlogN+Q)\mathcal{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

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

Resources
Benq

implementation

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 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]).
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 O(NloglogN)\mathcal{O}(N\log \log N).

Problems

StatusSourceProblem NameDifficultyTags
JOIEasy
CCEasy
Baltic OINormal
DMOPCNormal
NOINormal
Show TagsD&C, DP, Knapsack, SRQ
PlatinumHard
Show TagsD&C, Matrix
CFHard

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!

PrevNext