# Divide & Conquer - SRQ

Authors: Benjamin Qi, Andi Qu

### Prerequisites

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

$A[l]⊖A[l+1]⊖⋯⊖A[r]$where $⊖$ denotes an associative operation.

In the prerequisite module, it was shown that we can get $O(1)$ time queries with $O(NgN)$ time preprocessing when $⊖$ denotes `min`

. But how do we generalize to other associative operations?

We can use **divide & conquer** to answer $Q$ queries offline in $O((N+Q)gN)$ time or online in $O(NgN+Q)$.

## Offline Queries

Suppose that all queries satisfy $L≤l≤r≤R$ (initially, $L=1$ and $R=N$). Letting $M=⌊2L+R ⌋$, we can compute

$lef[l]=A[l]⊖A[l+1]⊖⋯⊖A[M]$for all $L≤l≤M$ and

$rig[r]=A[M+1]⊖A[M+2]⊖⋯⊖A[r]$for each $M<r≤R$. Then the answer for all queries satisfying $l≤M<r$ is simply $lef[l]⊖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 $O(NgN)$ 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]$. 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])`

.

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 maskif (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]);

A data structure known as **sqrt-tree** can speed up preprocessing time and memory to $O(NggN)$.

## Problems

Status | Source | Problem Name | Difficulty | Tags | Solution | URL |
---|---|---|---|---|---|---|

JOI | Easy | |||||

CC | Easy | Check CC | ||||

Baltic OI | Normal | |||||

DMOJ | Normal | Check DMOJ | ||||

Plat | Hard | External 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.