Hello Everyone,
There are many solutions for LCA query,like simple O(N) by traversal only,O(log(N)^2) using Binary lifting + Binary Search,Also most famous O(log(N)) solution. But recently I when I was learning about sparse table, I accounted with O(1) sol for each query using Euler Tour+RMQ using Sparse table. I tried to submit sol using this on SPOJ and CSES problem set and got accepted.
SPOJ Submission
#include "bits/stdc++.h"
using namespace std;
#define for1(i,a,b) for(int i=a;i<b;i++)
#define pb push_back
const int N=5e5+5;
int log1[N],first1[N],vis[N];
vector<int> adj[N],euiler,old_ind;
void dfs(int i,int par){
int new_ind=old_ind.size();
old_ind.push_back(i);
first1[i]=euiler.size();
euiler.push_back(new_ind);
for(int x:adj[i]){
if(x!=par){
dfs(x,i);
euiler.push_back(new_ind);
}
}
}
void sparse(int n,vector<vector<int>> &v){
int p=log1[n];
vector<int> v1(n+1,0);
for(int i=0;i<=p;i++) v.push_back(v1);
for(int i=1;i<=n;i++){
v[0][i]=euiler[i];
}
for(int j=1;j<=p;j++){
int len=(1<<j);
int len1=len/2;
for(int i=1;i+len-1<=n;i++){
v[j][i]=min(v[j-1][i],v[j-1][i+len1]);
}
}
}
int query(int l,int r,vector<vector<int>> &v){
int len=r-l+1;
int p=log1[len];
return min(v[p][l],v[p][r+1-(1<<p)]);
}
int main()
{
ios_base::sync_with_stdio(false);cin.tie(NULL);
for(int i=2;i<N;i++){
log1[i]=1+log1[i/2];
}
int t;cin>>t;
int kk=1;
while(t--){
vector<vector<int>> v;euiler.clear();
old_ind.clear();
cout<<"Case "<<kk++<<":"<<endl;
int n,m,u1,u2;cin>>n;
for1(i,1,n+1){
cin>>m;
while(m>0){
m--;
cin>>u1;adj[i].pb(u1);vis[u1]=1;
}
}
int root;
for1(i,1,n+1){
if(vis[i]==0){
root=i;break;
}
}
dfs(root,-1);
sparse(euiler.size(),v);
int q,l,r,ind1,ind2,ind;cin>>q;
while(q--){
cin>>l>>r;
ind1=first1[l];ind2=first1[r];
if(ind1>ind2){
swap(ind1,ind2);
}
ind=query(ind1,ind2,v);
cout<<old_ind[ind]<<endl;
}
for1(i,1,n+1){
vis[i]=0;
adj[i].clear();
}
}
return 0;
}
CSES Submission
#include "bits/stdc++.h"
//#include <algorithm>
#define ll long long
#define mod 1000000007
#define mk make_pair
#define pb push_back
#define fi first
#define se second
#define umap unordered_map
#define uset unordered_set
#define lb lower_bound
#define ub upper_bound
#define endll "\n";
#define all(x) (x).begin(), (x).end()
#define forr(it,x) for(auto it=x.begin();it!=x.end();it++)
#define for1(i,a,b) for(int i=a;i<b;i++)
#define for2(i,a,b) for(int i=a;i>=b;i--)
#define for3(i,a,b) for(long long int i=a;i<b;i++)
#define for4(i,a,b) for(long long int i=a;i>=b;i--)
#define pp pair<int,int>
#define ld long double
#define pll pair<ll,ll>
#define vll vector<ll>
#define vpp vector<pp>
#define vi vector<int>
#define vpll vector<pll>
#define vld vector<ld>
#define vvld vector<vld>
#define vvi vector<vi>
#define vvll vector<vll>
#define vvpll vector<vpll>
#define vvpp vector<vpp>
#define I insert
#define mem(a,x) memset(a,x,sizeof(a))
#define p_queue(a) priority_queue<a,vector<a>,greater<a>>
using namespace std;
const int N=5e5+5;
vi adj[N];
int log1[N],first1[N];
vector<int> euiler,old_ind;
void dfs(int i,int par){
int new_ind=old_ind.size();
old_ind.push_back(i);
first1[i]=euiler.size();
euiler.push_back(new_ind);
for(int x:adj[i]){
if(x!=par){
dfs(x,i);
euiler.push_back(new_ind);
}
}
}
void sparse(int n,vector<vector<int>> &v){
int p=log1[n];
vector<int> v1(n+1,0);
for(int i=0;i<=p;i++) v.push_back(v1);
for(int i=1;i<=n;i++){
v[0][i]=euiler[i];
}
for(int j=1;j<=p;j++){
int len=(1<<j);
int len1=len/2;
for(int i=1;i+len-1<=n;i++){
v[j][i]=min(v[j-1][i],v[j-1][i+len1]);
}
}
}
int query(int l,int r,vector<vector<int>> &v){
int len=r-l+1;
int p=log1[len];
return min(v[p][l],v[p][r+1-(1<<p)]);
}
int main()
{
ios_base::sync_with_stdio(false);cin.tie(NULL);
for(int i=2;i<N;i++){
log1[i]=1+log1[i/2];
}
vector<vector<int>> v;
int n,u1,q;cin>>n>>q;
for1(i,2,n+1){
cin>>u1;
adj[u1].push_back(i);
}
dfs(1,-1);
sparse(euiler.size(),v);
int l,r,ind1,ind2,ind;
while(q--){
cin>>l>>r;
ind1=first1[l];ind2=first1[r];
if(ind1>ind2){
swap(ind1,ind2);
}
ind=query(ind1,ind2,v);
cout<<old_ind[ind]<<endll;
}
return 0;
}
Now I have only one doubt that is this O(1) solution has any flaw?
If yes,what?
And if not,as far as I know this sol is not so famous compared to log(N) sol,why? even it is easy to code.It might possible that it is famous but I didn't know that.
Auto comment: topic has been updated by rajkumar62506 (previous revision, new revision, compare).
Yes, Using RMQ tables is O(1) because you divide the range L..R at some inner point say M and query(L..M) and query(M..R) [Here the L..M and M..R can overlap] and take the minimum of those two to get the LCA. This is fine for minimum (and hence to get LCA) as overlap does not matter.
But the same, cannot be done for other operations like sum, or etc. To do these operations we need to divide L..R in exclusive non-overlapping intervals which binary lifting does in O(log n).
Absolutely right.Sparse Table is good for idempotent functions,like min,max,gcd,lcm etc.
I see you're using a
log2array, but it's not actually needed. I think this will be slightly faster:31-__builtin_clz(n-1)will give the largestksuch that2^k <= n.Ok.I will try this. Thnx for knowledge.
Actually there is an even simpler way to do this, just use the
__lg()function.This is usually my go-to (the Sparse Table in my library is prewritten for this), but binary lifting also allows you to access the K-th ancestor of any node.