Task on array

Revision en3, by grimalk, 2015-08-04 22:14:41

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?

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)