I saw the following problem some time ago in a Russian Olympiad:
You are given $$$N$$$ $$$(1 \leq N \leq 10^4)$$$ integers in an array $$$(-10^9 \leq a_i \leq 10^9)$$$. There are Q queries that need to be answered online: — What is the minimum absolute difference of any two numbers in the range $$$[L, R]$$$?
Constraints:
- $$$(1 \leq N \leq 10^4)$$$
- $$$(1 \leq Q \leq 10^5)$$$
- $$$(-10^9 \leq a_i \leq 10^9)$$$
- $$$(1 \leq L \leq R \leq N)$$$
If anyone can give a hint or a solution, it would be greatly appreciated. I don't have a link to the original problem, if anyone has it, please put it in the comments.
I was thinking about SQRT decomposition and Segment trees, but you can't merge blocks/nodes easily. Also, using persistent segment trees doesn't really work for ranges, other than prefixes. Any ideas?
Edit: I solved it using SQRT decomposition. Solution