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+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.
