Äåðåâî ïî íåÿâíîìó êëþ÷ó.

n, a[] 

insert(i, x)
delete(i)
get(i)

Time = O(logn)

1. vector <int>, ArrayList <Integer>
insert = O(n)
delete = O(n)
get = O(1)

2.
insert = O(1)
delete = O(1)
get = O(m) // m -- queries

3.
BST ïî íåÿâíîìó êëþ÷ó
insert = delete = get = O(logn)

BST = balanced search tree

// search tree

struct tree;
typedef tree* ptree;

struct tree
{
  static ptree empty;

  ptree l, r;
  int x, size;

  tree( int x ) : l(empty), r(empty), x(x), size(0) { }
};

ptree tree::empty = new tree(-1);

// Add(x) x_1 <= x_2 <= ... <= x_n
// x -- key
void Add( ptree &t, int x )
{
  if (t == tree::empty)
    t = new tree(x);
  else 
    Add(t->x > x ? t->l : t->r, x);
  t->size++;
}

// implicit key -- íåÿâíûé êëþ÷
// explicit key -- ÿâíûé êëþ÷

// z -- data
// i -- key
void Add( ptree &t, int i, int z )
{
  if (t == tree::empty)
    t = new tree(z);
  else if (t->l->size >= i)
    Add(t->l, i, z);
  else
    Add(t->r, i - t->l->size - 1, z);
  t->size++;
}

bool Find( ptree t, int x )
{
  if (t == 0)
    return 0;
  if (t->x == x)
    return 1;
  return Find(t->x > x ? t->l : t->r, x);
}

// min element y : y >= x
int LowerBound( ptree t, int x )
{
  if (t == 0)
    return -1;
  if (t->x < x)
    return LowerBound(t->r, x);

  int tmp = LowerBound(t->l, x);
  return tmp == -1 ? t->x : tmpl
}

// O(n)
void Out( ptree t )
{
  if (!t)
    return;
  Out(t->l);
  //a[n++] = t->x;
  printf("%d ", t->x);
  Out(t->r);
}