Help on a (possibly useful) point update range query variation

Problems and Contests
#1

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:

  1. given a,b,k, find the maximum value less than k over the range x[a] ... x[b]
  2. 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

#2

This should be possible with a segment tree. Not sure about the implementation details though.

1 Like
#3

On a static array, you can do (1) using a persistent segment tree. You can do point or range updates in O(\log ^2N) using a segment tree of sets (for every range of values in the segment tree, store a set of all positions with values in that range).

1 Like