Out of curiosity and domain ignorance, why is the performance of something like your scheduling example something that needs to be optimized so much that you’ve tried so many structures already to no avail?
In this specific case, it’s part of an automatic scheduler that performs hundreds of thousands of range queries in a real-time interactive use case, so small improvements here can make a huge difference to the overall feel of the application. A lot of scheduling applications take seconds or minutes to run queries like that, but that would be way too slow for real-time interactions like I’m doing.
The current approach I’m using takes tens of milliseconds for some large test cases (which is great!), however I’d like to improve on it more so I could eventually run much bigger cases at real-time interactive speeds too.
Does the range query aggregate the elements in range? If the aggregation operation forms a group (follows associativity law, has inverse) you can use prefix sum data structures like Fenwick tree.
If it doesn't have inverse so that you cannot subtract prefix sum, sparse table can be used.
