blabla

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <limits>

template<typename T>
class SparseTable {
private:
  T **table;
  int height;
  long size;
  std::vector<int> *logarithm;

  void build_logarithm_floor(long n) {
    logarithm = new std::vector<int>(n + 1);
    for (long i = 0; i < n + 1; i++)
      (*logarithm)[i] = floor(log2(i + 1));
  }
public:
  SparseTable(std::vector<T> &array) {
    size = array.size();
    build_logarithm_floor(size);
    height = (*logarithm)[logarithm->size() - 1] + 1;
    long memory_in_bytes = height*sizeof(T *);
    memory_in_bytes += size*sizeof(T);
    long adder = size;
    for (int i = 1; i < height; i++) {
      memory_in_bytes += (adder - (1 << (i - 1)))*sizeof(T);
      adder -= (1 << (i - 1));
    }
    table = (T **)malloc(memory_in_bytes);
    //printf("Table memory consumption is %ld bytes\n", memory_in_bytes);
    //printf("plus %ld bytes on logarithm cache\n", logarithm->size()*sizeof(T));

    table[0] = (T *)(table + height);
    for (int i = 0; i < size; i++) {
      table[0][i] = array[i];
    }
    adder = size;
    for (int i = 1; i < height; i++) {
      table[i] = table[i - 1] + adder;
      for (int j = 0; j < adder - (1 << (i - 1)); j++) {
        table[i][j] = std::min(table[i - 1][j], table[i - 1][j + (1 << (i - 1))]);
      }
      adder -= (1 << (i - 1));
    }
  }
  ~SparseTable() {
    free(table);
    delete logarithm;
  }

  T rmq(long i, long j) {
    if (i == j) return table[0][i];
    int k = (*logarithm)[j - i];
    return std::min(table[k][i], table[k][j - (1 << k) + 1]);
  }
};

template<typename T>
class IntervalTree {
private:
  T *data;
  long size;
  const T INF = std::numeric_limits<T>::max() - 1;
public:
  IntervalTree(std::vector<T> &array) {
    long n = (1 << ((static_cast<int>(floor(log2(array.size() - 1))) + 1))) - 1;
    data = new T[2*n + 1];
    for (long i = n, len = n + array.size(); i < len; i++)
      data[i] = array[i - n];
    for (long i = n + array.size(); i < 2*n + 1; i++)
      data[i] = INF;

    for (long i = n - 1; i >= 0; i--)
      data[i] = std::min(data[2*i + 1], data[2*i + 2]);
    size = 2*n;
    for (long i = 0; i < size; i++)
      std::cout << data[i] << " ";
    std::cout << std::endl;
  }

  T rmq(long l, long r) {
    T ans = INF;
    long n = size / 2;
    l += n, r += n;
    while (l <= r)
    {
      // если l - правый  сын своего родителя, 
      // учитываем  его фундаментальный   отрезок
      if (!(l & 1))
          ans = std::min(ans, data[l]);
      // если r - левый сын своего родителя, 
      // учитываем его фундаментальный отрезок
      if ((r & 1))
          ans = std::min(ans, data[r]);
      // сдвигаем указатели на уровень выше
      l = (l) / 2, r = (r - 2) / 2;
      //std::cout << "ans: " << ans << std::endl;
    }   
    return ans;
  }

  ~IntervalTree() {
    delete[] data;
  }
};

void compute_tree(int *A, int *T, int n)
{
  int st[n], i, k, top = -1;
 
//we start with an empty stack
//at step i we insert A[i] in the stack
  for (i = 0; i < n; i++) {
//compute the position of the first element that is 
//equal or smaller than A[i]
    k = top;
    while (k >= 0 && A[st[k]] > A[i])
      k--;
//we modify the tree as explained above
    if (k != -1)
      T[i] = st[k];
    if (k < top)
      T[st[k + 1]] = i;
//we insert A[i] in the stack and remove 
//any bigger elements
      st[++k] = i;
      top = k;
  }
//the first element in the stack is the root of 
//the tree, so it has no father
  T[st[0]] = -1;
}

int main() {
  int data[14] = {0, 0, 0, 1, 1, 1, 1, 3, 0, 2, 2, 0, 2, 2};
  std::vector<int> lcp = std::vector<int>(data, data + sizeof(data)/sizeof(int));
  SparseTable<int> st = SparseTable<int>(lcp);
  IntervalTree<int> it = IntervalTree<int>(lcp);

  //int *tree_data = new int[14];
  //compute_tree(data, tree_data, 14);

  for (long i = 0; i < 14; i++) {
    for (long j = i; j < 14; j++) {
      printf("i = %ld, j = %ld, %d::%d\n", i, j, st.rmq(i, j), it.rmq(i, j));
    }
  }
  //printf("\n");
  //for (int i = 0; i < 14; i++)
  //  printf("%d ", tree_data[i]);
  //printf("\n");


  return 0;
}