ADJA's blog

[Tutorial] Sparse table
By ADJA, 6 years ago, In English

Hello, CF community.

I am starting to write about algorithms for fun and to spread the knowledge. Please read my new article about sparse table – a cute data structure to find range minimums in an array:

http://adilet.org/blog/sparse-table/

P.S. A little bit about myself: I was active in the competitive programming a while ago, especially during my two ACM ICPC World Finals in 2014 and 2015. Currently, I am working for Google and trying to revive some old algorithms knowledge :)

Would you be interested in the future algorithm articles like this? Follow me on twitter here: twitter.com/adiletzx

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

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

I can't find tutorials of other algos in your blog, They used to be there sometime back. will you please restore them?

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

    Hi! I didn't really have any other algorithm tutorials in my blog. Maybe you are thinking about my collection of algorithm implementations. I used to have it partially on my website, but now it's all on GitHub.

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

The Explanation is fairly Lucid and easy to comprehend, Thank You!

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

The tutorial was very helpful & easy to understand.Thank you very much :)

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

The tutorial was presented very nicely. It would be very helpful if you write more such blogs.

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

Waiting For other Tutorials too

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

what do you do if 2^i+j is greater than the length of your array?

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

    Not sure where you are coming from, but you iterate $$$i$$$ only up to $$$ \left \lfloor{log(n)}\right \rfloor $$$, and also you iterate $$$i$$$ and $$$j$$$ such that the range is never beyond the array. Please take one more look at the code :)

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

Quality content! Thanks for the blog

→ Reply