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.
Comments
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.