Дан массив V целых чисел.

Нужно обрабатывать следующие два типа запросов

1. Запрос содержит L, R, A, B, требуется посчитать, сколько таких j, что A ≤ j ≤ B и L ≤ V_j ≤ R

2. Запрос содержит i и X, V_i = X

Один человек сказал мне, что это невозможно решить с асимптотикой O(log n) на запрос.

Правда ли это? Будет неплохо увидеть доказательство того, что это правда или решение, если это утверждение неверно.

(Также мне были интересны другие асимптотики, которые могут быть лучше чем O(log n).)