Rare
0/6

# 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,A,\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 the prerequisite module, it was shown that we can get $O(1)$ time queries with $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 $O((N+Q)\log N)$ time or online in $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

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(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]\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[i]=comb(i,9) for i in [0,9]
• dat[i]=comb(10,i) for i in [10,19]
• dat[i]=comb(i,4) for i in [0,4]
• dat[i]=comb(5,i) for i in [5,9]
• dat[i]=comb(i,14) for i in [10,14]
• dat[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 XOR mask, which is 0. So our answer is min(dat,dat).
• To query comb(12,18) we first count the number of training zeroes in mask XOR mask, which is 1. So our answer is min(dat,dat).
1int n,q;2vi x, ans;3 4int dat[MX], mask[MX]; // 18 = ceil(log2(n))5 6void divi(int l, int r, int lev) { // generate dat and mask7    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(N\log \log N)$.

## Problems

StatusSourceProblem NameDifficultyTagsSolution
JOIEasy
CCEasyCheck CC
Baltic OINormal
DMOJNormalCheck DMOJ
PlatHardExternal Sol