Introduction

Given an integer array of size n.

There are m queries, each query consists of two integers x and y, asking for the maximum value in the range [x, y] of the array.

Approach

A straightforward method would be to precompute f[i][j] representing the maximum value from index i to j. However, this approach is inefficient.

Instead, we can use a technique similar to binary lifting to build a Sparce Table (ST table). Let st[i][j] denote the maximum value in the interval [i, i + 2^j - 1].

Initialization: st[i][0] = a[i]. Based on this definition, we can split the interval [i, i + 2^j - 1] into [i, i + 2^(j-1) - 1] and [i + 2^(j-1), i + 2^j - 1].

This leads to the recurrence relation:

for(int j=1; j<=lg[n]; j++) // Precompute floor(log2(i)), lg[1]=0, lg[i]=lg[i/2]+1
{
	for(int i=1; i<=n-(1<<j)+1; i++) 
	{
		st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
	}
}

Once the ST table is built, we process queries. For a range [l, r], we decompose it into segments based on powers of two.

Since we're dealing with maximum values, overlapping segments are allowed. We divide the interval into two parts:

If j = log2(r - l + 1), then we split into [l, l + 2^j - 1] and [r - 2^j + 1, r].

while(q--) 
{
	int l,r;
	cin>>l>>r;
	int j=lg[r-l+1];
	cout<<max(st[l][j],st[r-(1<<j)+1][j])<<"\n";
}

Combining these steps yields an efficiant solution.

Complete implementation:

#include<bits/stdc++.h>
#define int long long
#define PII pair<int,int>
#define ll long long
using namespace std;
const int N=1e5+5;
int lg[N];
int st[N][30];
int n,a[N],q;
signed main() {
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	lg[1]=0;
	for(int i=2; i<=N; i++) lg[i]=lg[i/2]+1;
	cin>>n>>q;
	for(int i=1; i<=n; i++) {
		cin>>a[i];
		st[i][0]=a[i];
	}
	for(int j=1; j<=lg[n]; j++) {
		for(int i=1; i<=n-(1<<j)+1; i++) {
			st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
		}
	}
	while(q--) {
		int l,r;
		cin>>l>>r;
		int j=lg[r-l+1];
		cout<<max(st[l][j],st[r-(1<<j)+1][j])<<"\n";
	}
	return 0;
}

Application —— Lowest Common Ancestor (LCA)

Problem Statement

Given a rooted tree with N nodes (numbered from 1 to N, where 1 ≤ N ≤ 10000), find the lowest common ancestor (LCA) of two specified nodes.

Approach

A naive method involves traversing upward from both nodes until a common ancestor is found. This is inefficient.

An optimization is to bring both nodes to the same level before ascending.

However, even with this improvement, performance issues may arise under tight constraints. Using binary lifting allows us to jump up the tree in powers of 2.

We precompute a 2D array f[i][j], where f[i][j] represents the 2^j-th ancestor of node i. This can be computed during tree traversal.

Initialize f[i][0] = parent[i]. Then, f[i][j] is defined as the 2^(j-1)-th ancestor of the 2^(j-1)-th ancestor of i:

f[i][j] = f[f[i][j-1]][j-1]

void dfs(int u)
{
	b[u]=1;
	for(int j=1;;j++)
	{
		f[u][j]=f[f[u][j-1]][j-1];
		if(f[u][j]==0)
		{
			k=max(k,j-1); // Determine maximum valid j
			break;
		}
	}
	for(auto it:v[u])
	{
		if(b[it]==0)
		{
			d[it]=d[u]+1; // Depth
			f[it][0]=u;
			dfs(it);
		}
	}
}

After preprocessing, we solve queries by first aligning both nodes to the same depth.

if(d[u]<d[v]) swap(u,v); // Ensure u is deeper
for(int j=k;j>=0;j--)
{
	if(d[f[u][j]]>=d[v]) 
	{
		u=f[u][j];
	}
}
if(u==v) return u; // Special case

Then, we simultaneously move both nodes upward until they meet.

for(int j=k;j>=0;j--)
{
	if(f[u][j]!=f[v][j]) // If not equal, proceed
	{
		u=f[u][j];
		v=f[v][j];
	}
}
return f[u][0]; // Return the result

Template code (note line 63):

#include
#define int long long
#define PII pair
#define ll long long
using namespace std;
const int N=1e4+5;
int lg[N],in[N];
int n,q,k,root;
int f[N][30];
int d[N];
bool b[N];
vector v[N];
void dfs(int u)
{
b[u]=1;
for(int j=1;;j++)
{
f[u][j]=f[f[u][j-1]][j-1];
if(f[u][j]==0)
{
k=max(k,j-1);
break;
}
}
for(auto it:v[u])
{
if(b[it]==0)
{
d[it]=d[u]+1;
f[it][0]=u;
dfs(it);
}
}
}
int lca(int u,int v)
{
if(d[u]=0;j--)
{
if(d[f[u][j]]>=d[v])
{
u=f[u][j];
}
}
if(u==v) return u;
for(int j=k;j>=0;j--)
{
if(f[u][j]!=f[v][j])
{
u=f[u][j];
v=f[v][j];
}
}
return f[u][0];
}
signed main()
{
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
d[0]=-1; // Essential! Prevent jumping to 0
cin>>n;
for(int i=1;i>x>>y;
v[x].push_back(y);
in[y]++;
}
root=0;
for(int i=1;i>q;
while(q--)
{
int x,y;
cin>>x>>y;
cout