Task on array

Правка en2, от grimalk, 2015-08-04 21:49:43

Given array V of integers.

Need to answer query of one type:

Given L, R, A, B, need to count how many A ≤ j ≤ B are so that L ≤ Vj ≤ R

Someone told me that this is impossible task in O(log n).

Is this true? Can anyone prove me that or prove it being wrong?

История

 
 
 
 
Правки
 
 
  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)