OLYMPIADS IN INFORMATICS, 2015, Vol. 9, pp. 39 - 44
© IOI, Vilnius University

ISSN 1822-7732

DOI: 10.15388/ioi.2015.04

Efficient Range Minimum Queries using Binary Indexed Trees

Mircea DIMA 1 , Rodica CETERCHI 2

1 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: mircea@hickery.net, rceterchi@gmail.com

Abstract

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.

Keywords:

binary indexed tree (BIT), least significant non-zero bit (LSB), range minimum query (RMQ).


PDFTo preview full article text in PDF format click here

Get Free ReaderYou could obtain free Acrobat Reader from Adobe


Copyright © International Olympiads in Informatics, Vilnius University Institute of Mathematics and Informatics, 2015