LCA

Tutorial

Implementation

Copy
import java.io.*;
import java.util.*;

public class LCA {
	public static int[] euler_tour, tin;
	public static int timer, size, N;
	public static ArrayList<Integer> g[];

	// Segtree code
	public static final int maxsize = (int)1e7;  // limit for array size

Sparse Tables

The above code does $\mathcal{O}(N)$ time preprocessing and allows LCA queries in $\mathcal{O}(\log N)$ time. If we replace the segment tree that computes minimums with a sparse table, then we do $\mathcal{O}(N\log N)$ time preprocessing and query in $\mathcal{O}(1)$ time.

The following is an example implementation of a sparse table and code that answers LCA queries. Build time is $\mathcal{O}(N\log N)$, and queries are $\mathcal{O}(1)$.

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

template <typename T> class SparseTable {
  private:
	int n, log2dist;
	vector<vector<T>> st;

  public:
	SparseTable(const vector<T> &v) {

Resources

Implementation

Problems