_VanGogh_'s blog

something like RMQ with BIT
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 [0, 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 :) note that this is not the same as RMQ and our intervals start from 0!

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

Comments Comments (21)
| Write comment?
»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Maybe you're asking about simple segment tree. Try to google "minimum query segment tree" in google.

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

Finally an expert from AE. Congratulations sepanta. You have what you could not ever imagine ;)

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +6 Vote: I do not like it

everything I know is this contest must be unrated for sepanta that's really bad that you can earn ratings eeeeeasily in CF

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    Agree! There were an announcement in contest for that (sepanta 35 раз уже взломал Mr_Fox, явно читерит) but nothing changed! hope cheaters never cheat again :)

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +39 Vote: I do not like it

    He is probably busy at the onsite event and will remove the cheater later.

    → Reply
»
8 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Auto comment: topic has been updated by _VanGogh_ (previous revision, new revision, compare).

→ Reply
»
8 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Am I missing something?

→ Reply
»
8 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Interest how this blog changed from reporting cheater to RMQ with BIT...

→ Reply
»
8 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Yes you can use BIT for RMQ for intervals starting from 1st position, but why change your blog post from Cheater Report to this all of a sudden?
I hope CF has enough pages, so you can start this discussion in a separate post and avoid all the confusion people are going to face after reading the initial comments.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it -24 Vote: I do not like it

    I understand what you are saying but I don't like a man become well known because of cheating and I changed my mind! let's forget everything!

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it -20 Vote: I do not like it

    could you please explain how can I do that with BIT?

    → Reply
»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it

As far as I know, you can do this if the new value is less or equal to the previous stored value.

→ Reply