Given a circular array A, how would you construct a segment tree off of A? Do you use two separate arrays for the segment tree or some other method?
If possible, it would also be very helpful if someone could explain how the range update and range queries would work for such a case.
Thanks!
>Solution :
We only use segment trees for associative operations, like "sum" and "min" and "xor", where if I give you the result for [start, mid) and [mid, end), you can directly compute the result for [start, end).
So you don’t actually need to do anything special for circular arrays; you can build and maintain your segment tree exactly the same as if the array were not interpreted as circular. To compute the result for an interval of the form [greater_index, lesser_index) that wraps around the end of the array, just use the normal method to compute the results for [greater_index, array_size) and [0, lesser_index), and combine them as normal.