Dynamite's blog

RMQ
By Dynamite, 10 years ago, In English

I need help on RMQ . How can I use RMQ in case of updatation ? Suppose , I have to find Min/max value between range and I have query of update . can it be done by RMQ ? Also how can I find Range Sum Query with this technique -------------------. I have already read topcoder tutorials

  • Vote: I like it
  • +3
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

To update a RMQ I think you need to re-process that bucket again. You can made a Range Sum Query with "RMQ", but it would be better and simpler to uso a Fenwick Tree. There are some good articles about it on topcoder: http://www.topcoder.com/tc?d1=tutorials&d2=lowestCommonAncestor&module=Static http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You mean answer RMQ problems where the array can be changed? If so, I recommend you to learn segment tree.

→ Reply