Really cool method! I wouldn't have thought it even possible to do RMQ in , and you explained the idea very well. Some small stuff 1. I thought RMQ stands for "range minimum query" and is a generic term for any data structure that solves this problem. This specific one is often called "sparse table", I believe. 2. Why do you take logn = 32? Typically the maximum allowed is around 6e7 ints for which logn ~ 26 and usually rmq problems have logn ~ 20 to allow nlgn memory I think most people would be familiar with "sliding window minimum" algorithm, this seems to be the idea, for the small blocks case except here the blocks are so small that you can represent all of them with a single integer which helps with the memory.

counting trailing zeroes takes log(n) [or say O(32), but that's a high constant] time I guess. Am I right?

Yup, this is something I haven't found anywhere else on KZfaq

Did he made a video on that ?

It was first explained to me by Andrew He at a bytedance camp in Beijing last year. I got some inspiration for implementation details from jcg on this blog post: codeforces.com/blog/entry/71706 Also, there is a really nice blog post written recently that gives good benchmarks for this version of the RMQ written by brunomont here: codeforces.com/blog/entry/78931

Thank you 🙂

If you did that, how would you handle queries where the size of the query is smaller than log?

Partial mins are only helpful if you know your range will always extend past the end of the block

Well yeah kinda. You can do it in real O(n) with some 4-russians nonsense, but that is WAY harder to explain and runs slower anyway, which is why I went with this. For actual contests, this is very useful because it uses 3*n integers, so you can use it for an array of size 10^7, which is what matters most to me

I don't follow. There are n/log(n) entries

@@fr5229 I am talking about 22:10. I knew the assumption that word size is greater than log(n) is going to somehow make the local runtime different than the asymptotic runtime. But I think I was wrong about where, like you said only 1 bit is being stored per element of the original sequence. However the assumption that log(n) bits can be checked in constant time is where the difference will come up. But maybe there is a way to do it with 4 russians making what I said unimportant anyway. It is a neat optimization and a good presentation, I shouldn't complain so much, but I do care about when people make claims about runtimes without making it clear that they aren't talking about asymptotic runtimes.

@@CarrotCakeMake Right, this will only work if the word size >= log(n). If you use 64 bit ints (which you can on a lot of platforms since they can do high/lo set bit with a single instruction) then your array size can be 2^64 and you would still have linear runtime total. As you said, not asymptotic, but could be made to work with ridiculously large inputs

@@CarrotCakeMake In the word RAM model, it is assumed that word size >= log(n), and operations on words are O(1), (like + - * /, bit operations), although what ops are allowed does change and this is maybe the weak point (if multiplication of words in O(1) is allowed or not makes a big difference). This is a decent model for a computer, because if the word size were smaller, you couldn't even index your input, because pointers, and memory locations also have to fit in a word. So in the word RAM model, the runtime is O(n log(n) / w), but since w>=log(n), this is at least as good as O(n). So this is not fake linear time, only linear time in a different (but frequently used) model.

It's a play off of the channel Algorithms Live

@@SecondThread 😮😮😮

lol fair enough. Potentially nontrivial LCA stuff starts at 7:36. I'll add the rest to the description