Task on array

Revision ru1, by grimalk, 2015-08-05 00:31:25

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

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

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

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

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

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

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

History

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