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 ≤ V_j ≤ R

2. Given i and X, V_i = 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(log² 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)