Task on array

Revision en6, by grimalk, 2015-08-05 00:42:28

Given array V of integers.

Need to answer query of two types:

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

  2. Given i and X, Vi = X

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?

It seems to be complicated. If anyone has any idea how to solve it faster than O(log2 n) I'd also like to hear that. O(log n * log max) is also pretty obvious solution (max is maximum value that can be stored in array)

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)