Binary search on segment trees starting at any position? (in O (log n ))

Правка en2, от tvan, 2020-10-20 15:39:20

Hello.

I have recently encountered a problem where I need to binary search on a segment tree starting at any position( there are no updates, but there isn't enough memory for a sparse table). The problem is that the time limit does not allow a O(logn ^2) binary search , so I'm wondering if there is a different approach. The segment tree is for maximums, so transforming the binary search by including the prefix then removing it is ( I think) not possible.

Thanks for your help !

Теги #segment-trees, #binary search, #segment tree, #help, #segmenttree

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский tvan 2020-10-20 15:39:20 8
en1 Английский tvan 2020-10-20 15:37:27 554 Initial revision (published)