Efficient Range Minimum Queries using Binary Indexed Trees
Hickery, Mircea DIMA, Rodica Ceterchi · OLYMPIADS IN INFORMATICS · 2015
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 (