We are given k segments (s_1,e_1),(s_2,e_2),(s_3,e_4),...,(s_k,e_k) where s_i <= e_i. Now we are given a query interval [L,R] to find the largest segment (s_i,e_i) contained within [L,R].
By the term largest we mean among all the segments contained within [L,R] return the one whose e_i-s_i is maximum.
And by term contained we mean L <= s_i <= e_i <= R
I am looking for an approach to answer the query in O(log(n)) where n = max(R_i)-min(L_i)
after some precomputation/tree-building etc costing no more than O(k log(n)). So if I have to answer q such queries my overall complexity should be O(k log(n) + q log(n)).
All the above values are integeral.
My views: Most probably it can be solved using a Segment tree + Lazy propagation.
Note that overall complexity I require is for online query ie lets just focus on solving for one query for now. For offline queries I found a solution here There it's mentioned that it can be solved for online too using Fractional cascading but doesn't quite explain it in detail.
The other related problem where I am trying to draw ideas from is this. For anyone who thinks they have something in mind please do refer these two resources.