Processing queries on multi-version data structure using an offline algorithm

offline.java

static void run(InputReader in, OutputWriter out) {
  
  int n = in.readRequestCount();
  
  children = new ArrayList[n];    // maximum number of versions is n
  relevantQueries = new ArrayList[n];
  for(int i = 0; i < n; ++i) {
    children[i] = new ArrayList<>();         // stores a list of versions that are directly produced from version i
    relevantQueries[i] = new ArrayList<>();  // stores a list of queries that are asked on version i
  }
  
  // 1. read input and build version tree
  int versionIndexer = 1, queryIndexer = 0;
  int curVersion = 0;
  while(n-->0) {
      Request r = in.readNextRequest();
      if(r.type == UPDATE) {
          // a new version will be produced from curVersion
          int nxtVersion = versionIndexer++;
          children[curVersion].add(new Edge(nxtVersion, r));
          curVersion = nxtVersion;
      }
      else if(r.type == QUERY) {
          // a new query is asked on curVersion
          int queryIndex = queryIndexer++;
          relevantQueries[curVersion].add(new Pair(queryIndex, r));
      }
  }
  
  // 2. answer all queries offline
  queryAnwer = new int[queryIndexer]; // queryAnswer[i] = answer of ith query
  ds = new MyDataStructure(); // data structure used for simulation -- initially empty
  solve(0);
  
  // 3. print answers according to input order
  for(int i = 0; i < queryIndexer; ++) {
      out.println(queryAnswer[i]);  
  } 
}

static ArrayList<Edge>[] children;
static ArrayList<Pair>[]  releventQueries;
static int[] queryAnswer;
static MyDataStructure ds;

static void solve(int v) {
    // ds now represents version v
    for(Pair queryPair: relevantQueries[v])
      queryAnswer[queryPair.queryIndex] = ds.answer(queryPair.query);
    
    // solve for all subtree
    for(Edge e: children[v]) {
        // apply operation that produces e.version from v
        ds.apply(e.update);
        // solve for e.version (and all its subtree)
        solve(e.version);
        // reverse operation that produces v from e.version
       ds.reverseApply(e.update); 
    }
  
}

static class Pair {
  int queryIndex;
  Query query;
  
  Query(int queryIndex, Query query) { /* init */ }
}

static class Edge {
  int version;
  Update update;
  
  Edge(int version, Update update) { /* init */ }
}