Дерево отрезков.
  1. get(i, x) : ближайший справа от i элемент >= x
  2. даны точки, запрос: есть ли в [y1..y2] [-inf..x] хотя бы одна точка?
  3. количество различных на отрезке в offline и online
  4. k-я порядковая статистика на отрезке в online
  5. количество различных чисел на меняющемся массиве в online
  6. k-я порядковая статистика на отрезке на меняющемся массиве в online
  7. k-я порядковая статистика среди различных чисел на отрезке на меняющемся массиве в online
  8. fractional cascading: даны k отсортированных массивов длины n, нужно за O(k + logn) возвращать для каждого массива количество элементов <= x
  9. IOI 2005: горки --- у каждого сегмента есть наклон (изменение высоты). Запросы: на отрезке присвоить наклон; узнать первую точку >= h
  10. Запросы: max= на отрезке, sum на отрезке

Корневая
  11. max=, min=, sum на отрезке
  12. k-я порядковая статистика для меняющегося массива
