Static Array Queries

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

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

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

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.

Solution - RMQ

Copy
#include <bits/stdc++.h>
using namespace std;

static const int MAXN = 200000 + 5;

int n, q, A[MAXN], B[MAXN];
vector<int> x, ans;
int lef[MAXN], rig[MAXN];

void divi(int l, int r, vector<int> v) {

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.

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]).

Copy
#include <bits/stdc++.h>
using namespace std;

static const int MAXN = 200000 + 5;

int n, q;
vector<int> x, ans;

int dat[18][MAXN];  // 18 = ceil(log2(n))
int mask[MAXN];

Problems