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.

## Static Array Queries

Focus Problem – read through this problem before continuing!

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

$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 $\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

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

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

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

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.

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

## Problems

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

### 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!