Task on array

Правка ru2, от grimalk, 2015-08-05 00:32:30

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

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

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

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

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

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

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

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
ru4 Русский grimalk 2015-08-05 00:44:23 139
en6 Английский grimalk 2015-08-05 00:42:28 111
ru3 Русский grimalk 2015-08-05 00:33:01 27
ru2 Русский grimalk 2015-08-05 00:32:30 2 Мелкая правка: 'чем $O(log$ $n)$.)' -> 'чем $O(log^2$ $n)$.)'
en5 Английский grimalk 2015-08-05 00:32:12 125
ru1 Русский grimalk 2015-08-05 00:31:25 561 Первая редакция перевода на Русский
en4 Английский grimalk 2015-08-04 22:17:24 12
en3 Английский grimalk 2015-08-04 22:14:41 39
en2 Английский grimalk 2015-08-04 21:49:43 0 (published)
en1 Английский grimalk 2015-08-04 21:49:32 301 Initial revision (saved to drafts)