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.↵
↵
<spoiler summary="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;↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
<spoiler summary="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;↵
}↵
~~~~~↵
</spoiler>↵
↵
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.
↵
↵
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.↵
↵
<spoiler summary="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;↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
<spoiler summary="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;↵
}↵
~~~~~↵
</spoiler>↵
↵
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.
