_VanGogh_'s blog

RMQ with changing option
By _VanGogh_, history, 8 years ago, In English

Is there an algorithm like RMQ that we can change our array elements??? It means that we have an array with all the elements equal to 0 at first.(number of elements < 1e5) and we have 2 types of queries: 1-change the i'th value 2-give the minimum value in range [li, ri] (number of queries < 1e5) I'm new to programming and found nothing on the web I'll be glad if you help me tnx :)

Tags rmq
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

you can use Segment tree for that, each query can be answered in logn time

you can check this

→ Reply