Constant time feasibility check of inserts and linear time update after insert.

Of course, there are tricks that support multiple simultaneous inserts and tricks that minimize the update of the data structure after insert.

But, if you want to do 2-opt (k-opt) with time windows, then you have to work out the details because no one in academia did.