Блог пользователя Dynamite

Автор Dynamite, 11 лет назад, По-английски

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

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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