In the past couple days I’ve come across several problems which would be made relatively simple if a certain type of range-query data structure existed, but haven’t yet figured out how to implement; I also have been unable to find references online. Does anyone know if this is possible/how to do it?
Requirements: support these operations on an array x of N elements in \log N time:
- given a,b,k, find the maximum value less than k over the range x[a] ... x[b]
- given a,k, update x[a] to the value k
Bonus points for range updates for (2), though if someone can do just (1) on a static array, I’d consider that cool as well. Thanks in advance for any help yall
EDIT: yea segtree seems legit, I’ve been trying and failing to actually figure out how