OLYMPIADS IN INFORMATICS, 2015, Vol. 9, pp. 39 - 44
© IOI, Vilnius University
Efficient Range Minimum Queries using Binary Indexed Trees
Mircea DIMA 1 , Rodica CETERCHI 2
Hickery, Martir Closca st., 600206 Bacau, Romania
2 University of Bucharest, Faculty of Mathematics and Computer Science 14 Academiei st., 010014 Bucharest, Romania
e-mail: firstname.lastname@example.org, email@example.com
We present new results on Binary Indexed Trees in order to efficiently solve Range Minimum Queries. We introduce a way of using the Binary Indexed Trees so that we can answer different types of queries, e.g. the range minimum query, in O(log N ) time complexity per operation, outperforming in speed similar data structures like Segment/Range Trees or the Sparse Table Algorithm.
binary indexed tree (BIT), least significant non-zero bit (LSB), range minimum query (RMQ).
To preview full article text in PDF format click here
You could obtain free Acrobat Reader from Adobe
Copyright © International Olympiads in Informatics, Vilnius University Institute of Mathematics and Informatics, 2015